Degree Bounded Spanning Trees

In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?_{v ? V(T)}max{d_T(v)-k,0} ￡ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} .     

Some results on odd factors of graphs

A {1, 3, …,2n ? 1}-factor of a graph G is defined to be a spanning subgraph of G, each degree of whose vertices is one of {1, 3, …, 2n ? 1}, where n is a positive integer. In this paper, we give a sufficient condition for a graph to have a {1, 3, …, 2n ? 1}-factor.     

Further results on the lower bounds of mean color numbers

Let G be a graph with n vertices. The mean color number of G, denoted by μ(G), is the average number of colors used in all n‐colorings of G. This paper proves that μ(G) ≥ μ(Q), where Q is any 2‐tree with n vertices and G is any graph whose vertex set has an ordering x₁,x₂,…,x_n such that x_i is contained in a K₃ of G[V_i] for i = 3,4,…,n, where V_i = {x₁,x₂,…,x_i}. This result improves two known results that μ(G) ≥ μ(O_n) where O_n is the empty graph with n vertices, and μ(G) ≥ μ(T) where T is a spanning tree of G. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 51–73, 2005     

Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:

• (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:
  • (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/3+c^1/(3r+3))n² edges.
  Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions:
  • (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/4+c^1/(8r+8))n² edges.
  © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009     

On resolvable tree-decompositions of complete graphs

A partition of the edge set of a graph H into subsets inducing graphs H₁,…,H_s isomorphic to a graph G is said to be a G-decomposition of H. A G-decomposition of H is resolvable if the set {H₁,…,H_s} can be partitioned into subsets, called resolution classes, such that each vertex of H occurs precisely once in each resolution class. We prove that for every graceful tree T of odd order the obvious necessary conditions for the existence of a resolvable T-decomposition of a complete graph are asymptotically sufficient. This generalizes the results of Horton and Huang concerning paths and stars.     

The independence number condition for the existence of a spanning f‐tree

Let G be a graph and f be a mapping from V(G) to the positive integers. A subgraph T of G is called an f‐tree if T forms a tree and d_T(x)≤f(x) for any x∈V(T). We propose a conjecture on the existence of a spanning f‐tree, and give a partial solution to it. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 173–184, 2010     

Some results on spanning trees

Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.     

Backbone colorings for graphs: Tree and path backbones

We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a backbone coloring for G and H is a proper vertex coloring V → {1,2,…} of G in which the colors assigned to adjacent vertices in H differ by at least two. We study the cases where the backbone is either a spanning tree or a spanning path. We show that for tree backbones of G the number of colors needed for a backbone coloring of G can roughly differ by a multiplicative factor of at most 2 from the chromatic number χ(G); for path backbones this factor is roughly . We show that the computational complexity of the problem “Given a graph G, a spanning tree T of G, and an integer ?, is there a backbone coloring for G and T with at most ? colors?” jumps from polynomial to NP‐complete between ? = 4 (easy for all spanning trees) and ? = 5 (difficult even for spanning paths). We finish the paper by discussing some open problems. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 137–152, 2007     

On the spectral radius of ‡-shape trees

Let A(G) be the adjacency matrix of G. The characteristic polynomial of the adjacency matrix A is called the characteristic polynomial of the graph G and is denoted by φ(G, λ) or simply φ(G). The spectrum of G consists of the roots (together with their multiplicities) λ ₁(G) ? λ ₂(G) ? … ? λ _n (G) of the equation φ(G, λ) = 0. The largest root λ ₁(G) is referred to as the spectral radius of G. A ?-shape is a tree with exactly two of its vertices having maximal degree 4. We will denote by G(l ₁, l ₂, … l ₇) (l ₁ ? 0, l _i ? 1, i = 2, 3, …, 7) a ?-shape tree such that $G\left( {l_1 ,l_2 , \ldots l_7 } \right) - u - v = P_{l_1 } \cup P_{l_2 } \cup \ldots P_{l_7 }$ , where u and v are the vertices of degree 4. In this paper we prove that ${{3\sqrt 2 } \mathord{\left/ {\vphantom {{3\sqrt 2 } 2}} \right. \kern-0em} 2} < \lambda _1 \left( {G\left( {l_1 ,l_2 , \ldots l_7 } \right)} \right) < {5 \mathord{\left/ {\vphantom {5 2}} \right. \kern-0em} 2}$ .     

Forest-Like Permutations

Given a permutation , construct a graph G _π on the vertex set {1, 2,..., n} by joining i to j if (i) i < j and π(i) < π(j) and (ii) there is no k such that i < k < j and π(i) < π(k) < π(j). We say that π is forest-like if G _π is a forest. We first characterize forest-like permutations in terms of pattern avoidance, and then by a certain linear map being onto. Thanks to recent results of Woo and Yong, these show that forest-like permutations characterize Schubert varieties which are locally factorial. Thus forest-like permutations generalize smooth permutations (corresponding to smooth Schubert varieties). We compute the generating function of forest-like permutations. As in the smooth case, it turns out to be algebraic. We then adapt our method to count permutations for which G _π is a tree, or a path, and recover the known generating function of smooth permutations. Received March 27, 2006     

The cycle space of an embedded graph

Let G be a connected graph with edge set E embedded in the surface ∑. Let G° denote the geometric dual of G. For a subset d of E, let τd denote the edges of G° that are dual to those edges of G in d. We prove the following generalizations of well-known facts about graphs embedded in the plane. (1) b is a boundary cycle in G if and only if τb is a cocycle in G°. (2) If T is a spanning tree of G, then τ(E/T) contains a spanning tree of G°. (3) Let T be any spanning tree of G and, for e ? E/T, let T(e) denote the fundamental cycle of e. Let U ∪ E/T. Then τU is a spanning tree of G° if and only if the set of face boundaries, less any one, together with the set {T(e); e ? E/(T ∪ U)} is a basis for the cycle space of G.     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K_2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a₁,…, a_k) is a color distribution for the complete graph K_n, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K_n with the above distribution if T is a non‐star multicolored spanning tree of K_n, then there exists a multicolored spanning tree T' of K_n such that T and T' are edge‐disjoint. Also it is shown that if K_n, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007     

Fundamental cycles and graph embeddings

In this paper, we investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T , there exists a sequence of fundamental cycles C1, C2, . . . , C2g with C2i-1 ∩ C2i≠ф for 1≤ i ≤g. In particular, among β(G) fundamental cycles of any spanning tree T of a graph G, there are exactly 2γM (G) cycles C1, C2, . . . , C2γM (G) such that C2i-1 ∩ C2i≠ф for 1 ≤i≤γM (G), w...     

Spanning 2‐trails from degree sum conditions

Suppose G is a simple connected n‐vertex graph. Let σ₃(G) denote the minimum degree sum of three independent vertices in G (which is ∞ if G has no set of three independent vertices). A 2‐trail is a trail that uses every vertex at most twice. Spanning 2‐trails generalize hamilton paths and cycles. We prove three main results. First, if σ₃G)≥ n ‐ 1, then G has a spanning 2‐trail, unless G ? K_1,3. Second, if σ₃(G) ≥ n, then G has either a hamilton path or a closed spanning 2‐trail. Third, if G is 2‐edge‐connected and σ₃(G) ≥ n, then G has a closed spanning 2‐trail, unless G ? K_2,3 or K (the 6‐vertex graph obtained from K_2,3 by subdividing one edge). All three results are sharp. These results are related to the study of connected and 2‐edge‐connected factors, spanning k‐walks, even factors, and supereulerian graphs. In particular, a closed spanning 2‐trail may be regarded as a connected (and 2‐edge‐connected) even [2,4]‐factor. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 298–319, 2004     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

Average distance,minimum degree,and spanning trees

The average distance μ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., μ(G) = ()⁻¹ Σ_{x,y}⊂V(G) d_G(x, y), where V(G) denotes the vertex set of G and d_G(x, y) is the distance between x and y. We prove that every connected graph of order n and minimum degree δ has a spanning tree T with average distance at most . We give improved bounds for K₃‐free graphs, C₄‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000     

Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,…,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n²?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n²?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1.     

Spanning tree formulas and chebyshev polynomials

The Kirchhoff Matrix Tree Theorem provides an efficient algorithm for determiningt(G), the number of spanning trees of any graphG, in terms of a determinant. However for many special classes of graphs, one can avoid the evaluation of a determinant, as there are simple, explicit formulas that give the value oft(G). In this work we show that many of these formulas can be simply derived from known properties of Chebyshev polynomials. This is demonstrated for wheels, fans, ladders, Moebius ladders, and squares of cycles. The method is then used to derive a new spanning tree formula for the complete prismR _n (m) =K _m ×C _n . It is shown that $$2^{\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)\left( {1 - \frac{1}{{r - 1}} + o\left( 1 \right)} \right)} $$ whereT _n (x) is then ^th order Chebyshev polynomial of the first kind.