On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

On decomposition of r-partite graphs into edge-disjoint hamilton circuits

Let K(n;r) denote the complete r-partite graph K(n, n,…, n). It is shown here that for all even n(r ? 1) ? 2, K(n;r) is the union of $\text{n(r ? 1)}\text{2}$ of its Hamilton circuits which are mutually edge-disjoint, and for all odd n(r ? 1) ? 1, K(n;r) is the union of $\text{(n(r ? 1) ? 1)}\text{2}$ of its Hamilton circuits and a 1-factor, all of which are mutually edge-disjoint.     

Triangles in arrangements of lines

A set of n lines in the projective plane divides the plane into a certain number of polygonal cells. We show that if we insist that all of these cells be triangles, then there are at most $\text{1}\text{3}\text{n(n ? 1) + 4 ?}\text{2}\text{7}\text{n}$ of them. We also observe that if no point of the plane belongs to more than two of the lines and n is at least 4, some of the cells must be either quadrangles or pentagons. We further show that for $\text{n ≧ 4}$, there is a set of n lines which divides the plane into at least $\text{1}\text{3}\text{n(n ? 3) + 4}$ triangles.     

Decomposition de Km+Kn en cycles hamiltoniens

Let K_m be the complete graph of order m. We prove that the cartesian sum K_m+K_n can be decomposed into $\text{1}\text{2}$(m+n?2) hamiltonian cycles if m+n is even and into $\text{1}\text{2}$(m+n?3) hamiltonian cycles and a perfect matching if m+n is odd.     

Extremal values of the interval number of a graph,II

It is shown that the interval number of a graph on n vertices is at most $\text{[}\text{1}\text{4}\text{(n+1)]}$, and this bound is best possible. This means that we can represent any graph on n vertices as an intersection graph in which the sets assigned to the vertices each consist of the union of at most $\text{[}\text{1}\text{4}\text{(n+1)]}$ finite closed intervals on the real line. This upper bound is attained by the complete bipartite graph K_[n/2],[n/2].     

Optimal crossing-free Hamiltonian circuit drawings of Kn

The number of crossing-free Hamiltonian circuits in planar drawings of K_n is studied. In particular, it is shown that for planar drawings of K_n, (1) there are drawings having as many as $\text{(}\text{3}\text{20}\text{)·10}{}^{\mathrm{<mtext>[</mtext><mtext>n</mtext><mtext>3</mtext><mtext>]</mtext>}}$ such circuits and (2) no drawing contains more than $\text{2·6}{}^{\mathrm{n?2}}\text{([}\text{n}\text{2}\text{])!}$     

Orientable and nonorientable genus of the complete bipartite graph

K_m,n is the complete bipartite graph with m and n vertices in its chromatic classes. G. Ringel has proved that the orientable genus of K_m,n is equal to $\text{{}\text{(m ? 2)(n ? 2)}\text{4}\text{}}\text{if}\text{m ≥ 2}\text{and}\text{n ≥ 2}$ and that its nonorientable genus is equal to $\text{{}\text{(m ? 2)(n ? 2)}\text{2}\text{}}\text{if}\text{m ≥ 3}\text{and}\text{n ≥ 3}$. We give new proofs of these results.     

Heuristic matching for graphs satisfying the triangle inequality

Two matching heuristics are presented. The hyper-greedy method runs in time O(n²log n) and produces a matching whose cost is at most 2log₃(1.5n) times optimal. Graphs are given causing this method to achieve nearly this ratio. The factor of two method runs in time O(n²log K), where K is the maximum ratio of edge lengths in the graph, and never requires more than O(n³) time. The factor of two method produces a matching whose cost is at most max(4log₂K, 4log₂n) times optimal, plus lower-order terms. Graphs are given causing this method to achieve a ratio asymptotically equal to $\text{(}\text{log}{}_2\text{n)}\text{2}$.     

2-Colored triangles in edge-colored complete graphs

If each edge of complete graph K_n is colored with one of k colors then it contains a triangle having two colors if $\text{k < 1 + n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. The result is best possible when n is the square of a prime.     

A combinatorial interpretation for two transformations of series that commute with compositional inversion

For a formal power series $\text{g(t) =}\text{1}\text{[1 + ∑}{}_{\mathrm{n=1}}{}^{\mathrm{\infty }}\text{h}{}_{\mathrm{n}}\text{t}{}^{\mathrm{n}}\text{]}$ with nonnegative integer coefficients, the compositional inverse $\text{f}\text{(t) = t · f(t)}$ of $\text{g}\text{(t) = t · g(t)}$ is shown to be the generating function for the colored planted plane trees in which each vertex of degree i + 1 is colored one of h_i colors. Since the compositional inverse of the Euler transformation of f(t) is the star transformation [[g(t)]^?1 ? 1]^?1 of g(t), [2], it follows that the Euler transformation of f(t) is the generating function for the colored planted plane trees in which each internal vertex of degree i + 1 is colored one of h_i colors for i > 1, and h₁ ? 1 colors for i = 1.     

The nonorientable genus of the symmetric quadripartite graph

The nonorientable genus of K_4(n) is shown to satisfy:

$\text{γ}\text{(K}{}_{\mathrm{4(n)}}\text{)=2(n?1)}{}^2\text{for n ? 3}$

,

$\text{γ}\text{(K}{}_{\mathrm{4(2)}}\text{)=3,}\text{γ}\text{(K}{}_4\text{(1))=1}$

.     

On ranges of Lyapunov transformations

A Lyapunov transformation is a linear transformation on the set $\text{H}$_n of hermitian matrices H ? $\text{C}$^n,n of the form $\text{L}$_A(H) = A¹H + HA, where A ?$\text{C}$^n,n. Given a positive stable A ?$\text{C}$^n,n, the Stein-Pfeffer Theorem characterizes those K ? $\text{H}$_n for which K = $\text{L}$_B(H), where B is similar to A and H is positive definite. We give a new proof of this result, and extend it in several directions. The proofs involve the idea of a controllability subspace, employed previously in this context by Snyders and Zakai.     

Rectangular arrays

In this paper we studied m×n arrays with row sums $\text{nr}\text{(n,m)}$ and column sums $\text{mr}\text{(n,m)}$ where (n,m) denotes the greatest common divisor of m and n. We were able to show that the function H_m,n(r), which enumerates m×n arrays with row sums and column sums $\text{nr}\text{(m,n)}$ and $\text{mr}\text{(n,m)}$ respectively, is a polynomial in r of degree (m?1)(n?1). We found simple formulas to evaluate these polynomials for negative values, ?r, and we show that certain small negative integers are roots of these polynomials. When we considered the generating function G_m,n(y) = Σ_r?0H_m,n(r)y^r, it was found to be rational of degree less than zero. The denominator of G_m,n(y) is of the form (1?y)^(m?1)(n?1)+3, and the coefficients of the numerator are non-negative integers which enjoy a certain symmetric relation.     

Positive operators on the n-dimensional ice cream cone

Let $\text{K}{}_{\mathrm{n}}\text{= {x ? R}{}^{\mathrm{n}}\text{: (x}{}_1{}^2\text{+ · +x}{}^2{}_{\mathrm{n?1}}\text{)}\text{1}\text{2}\text{? x}{}_{\mathrm{n}}\text{}}$ be the n-dimensional ice cream cone, and let Γ(K_n) be the cone of all matrices in $\text{R}$ⁿⁿ mapping K_n into itself. We determine the structure of Γ(K_n), and in particular characterize the extreme matrices in Γ(K_n).     

Relative locality of derivations

Let H and K be symmetric linear operators on a C¹-algebra $\text{U}$ with domains D(H) and D(K). H is defined to be strongly K-local if $\text{ω(K(A)}{}^1\text{K(A)) = 0}$ implies $\text{ω(H(A)}{}^1\text{H(A)) = 0}$ for A?D(H) ∩ D(K) and ω in the state space of $\text{U}$, and H is completely strongly K-local if $\text{Ω(K(A)}{}^1\text{K(A))=0}$ implies $\text{Ω(H(A)}{}^1\text{H(A))=0}$ for A ∈ D(H) ∩ D(K) and Ω in the state of $\text{U}$, and H is cpmpletely strongly K-local if $\text{H??}{}_{\mathrm{n}}$ is $\text{K??}{}_{\mathrm{n}}$-local on U?M_n for all n ? 1, where $\text{1}$_n is the identity on the n × n matrices M_n. If $\text{U}$ is abelian then strong locality and complete strong locality are equivalent. The main result states that if τ is a strongly continuous one-parameter group of ¹-automorphisms of $\text{U}$ with generator δ₀ and δ is a derivation which commutes with τ and is completely strongly δ₀-local then δ generates a group α of ¹-automorphisms of $\text{U}$. Various characterizations of α are given and the particular case of periodic τ is discussed.     

The interval number of a complete multipartite graph

The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line $\text{R}$. Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is $\text{?}\text{(mn + 1)}\text{(m + n)}\text{?}$. Matthews showed that the interval number of the complete multipartite graph K(n₁,n₂,…,n_p) was the same as the interval number of K(n₁,n₂) when n₁ = n₂ = ? = n_p. Trotter and Hopkins showed that i(K(n₁,n₂,…,n_p)) ≤ 1 + i(K(n₁,n₂)) whenever p ≥ 2 and n₁≥n₂≥ ? ≥n_p. West showed that for each n ≥ 3, there exists a constant c_n so that if p ≥ c_n,n₁ = n²?n ?1, and n₂ = n₃ = ? n_p = n, then i(K(n₁,n₂,…,n_p) = 1 + i(K(n₁, n₂)). In view of these results, it is natural to consider the problem of determining those pairs (n₁,n₂) with n₁ ≥ n₂ so that i(K(n₂,…,n_p)) = i(K(n₁,n₂)) whenever p ≥ 2 and n₂ ≥ n₃ ≥ ? ≥ n_p. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n² ? n ? 1, n) for n ≥ 3 and (7,5).     

A new solution for the nonorientable case 1 of the heawood Map Color Theorem

A simpler method for proving $\text{γ}\text{(K}{}_{\mathrm{n}}\text{) =}\text{(n ? 3)(n ? 4)}\text{6}$ when n ≡ 1 (mod 12).