Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

Spanning trees with variable degree bounds

In this paper, we introduce and study a generalization of the degree constrained minimum spanning tree problem where we may install one of several available transmission systems (each with a different cost value) in each edge. The degree of the endnodes of each edge depends on the system installed on the edge. We also discuss a particular case that arises in the design of wireless mesh networks (in this variant the degree of the endnodes of each edge depend on the transmission system installed on it as well as on the length of the edge). We propose three classes of models using different sets of variables and compare from a theoretical perspective as well as from a computational point of view, the models and the corresponding linear programming relaxations. The computational results show that some of the proposed models are able to solve to optimality instances with 100 nodes and different scenarios.     

Degree sums and spanning brooms of a graph

A broom is a tree obtained by identifying an endpoint of a path with the center of a star. Let G be a connected graph of order $n\ge 3$. Chen et al. [2] conjectured that if the degree sum is at least $n?2$ for any three pairwise nonadjacent vertices, then G contains a spanning broom. In this paper, we confirm the conjecture for $n>50$.     

Covering times of random walks on bounded degree trees and other graphs

The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)⁽¹⁾ andO(|V| |E|/d _min)⁽²⁾ imply an upper bound ofO(n ²). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log² n). The previous lower bound was (|V| log |V|) for trees.⁽²⁾ In our main result, we show a lower bound of (|V| (log _{d max} |V|)²) for trees, which yields a lower bound of (n log² n). We also extend our techniques to show an upper bound for general graphs ofO(max{E T_i} log |V|).     

Degree sum and connectivity conditions for dominating cycles

For a graph G, let σ_k(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n?3 with σ₂(G)?n then G is hamiltonian. Let κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with σ₃(G)?n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with σ₃(G)?n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with σ₄(G)?n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.     

On vertex-disjoint cycles and degree sum conditions

This paper considers a degree sum condition sufficient to imply the existence of $k$ vertex-disjoint cycles in a graph $G$. For an integer $t\ge 1$, let ${\sigma }_t\left(G\right)$ be the smallest sum of degrees of $t$ independent vertices of $G$. We prove that if $G$ has order at least $7k+1$ and ${\sigma }_4\left(G\right)\ge 8k?3$, with $k\ge 2$, then $G$ contains $k$ vertex-disjoint cycles. We also show that the degree sum condition on ${\sigma }_4\left(G\right)$ is sharp and conjecture a degree sum condition on ${\sigma }_t\left(G\right)$ sufficient to imply $G$ contains $k$ vertex-disjoint cycles for $k\ge 2$.     

On degree sum conditions for long cycles and cycles through specified vertices

Let G be a graph. For S⊂V(G), let Δ_k(S) denote the maximum value of the degree sums of the subsets of S of order k. In this paper, we prove the following two results. (1) Let G be a 2-connected graph. If Δ₂(S)≥d for every independent set S of order κ(G)+1, then G has a cycle of length at least min{d,|V(G)|}. (2) Let G be a 2-connected graph and X a subset of V(G). If Δ₂(S)≥|V(G)| for every independent set S of order κ(X)+1 in G[X], then G has a cycle that includes every vertex of X. This suggests that the degree sum of nonadjacent two vertices is important for guaranteeing the existence of these cycles.     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.     

Degree sum conditions for oriented forests in digraphs

Let F be an oriented forest with n vertices and m arcs and D be a digraph without loops and multiple arcs. In this note we prove that D contains a subdigraph isomorphic to F if D has at least n vertices and min{d⁺(u)+d⁺(v),d⁻(u)+d⁻(v),d⁺(u)+d⁻(v)}≥2m−1 for every pair of vertices u,v∈V(D) with uv∉A(D). This is a common generalization of two results of Babu and Diwan, one on the existence of forests in graphs under a degree sum condition and the other on the existence of oriented forests in digraphs under a minimum degree condition.     

The energy and spanning trees of the Aztec diamonds

The Aztec diamond was extensively studied in both graph theory and statistical physics. Knuth obtained a formula of the number of spanning trees of the Aztec diamond with the constrained boundary condition, which solved a conjecture posed by Stanley in 1994. In this paper, We give the formulae of the energy and the number of spanning trees of the Aztec diamond with the toroidal boundary condition.     

Weak cycle partition involving degree sum conditions

Let G be a graph of order n and k a positive integer. A set of subgraphs H={H₁,H₂,…,H_k} is called a k-degenerated cycle partition (abbreviated to k-DCP) of G if H₁,…,H_k are vertex disjoint subgraphs of G such that and for all i, 1≤i≤k, H_i is a cycle or K₁ or K₂. If, in addition, for all i, 1≤i≤k, H_i is a cycle or K₁, then H is called a k-weak cycle partition (abbreviated to k-WCP) of G. It has been shown by Enomoto and Li that if |G|=n≥k and if the degree sum of any pair of nonadjacent vertices is at least n−k+1, then G has a k-DCP, except G≅C₅ and k=2. We prove that if G is a graph of order n≥k+12 that has a k-DCP and if the degree sum of any pair of nonadjacent vertices is at least , then either G has a k-WCP or k=2 and G is a subgraph of K₂∪K_n−2∪{e}, where e is an edge connecting V(K₂) and V(K_n−2). By using this, we improve Enomoto and Li’s result for n≥max{k+12,10k−9}.     

A Flow Formulation for the Optimum Communication Spanning Tree

In this paper we address the Optimum Communication Spanning Tree Problem. We present a formulation that uses three index variables and we propose several families of inequalities, which can be used to reinforce the formulation. Preliminary computational experiments are very promising.     

Degree and neighborhood conditions for hamiltonicity of claw-free graphs

For a graph $H$, let ${\sigma }_t\left(H\right)=min\left\{{\Sigma }_{i=1}^t{d}_H\left(v_i\right)\right|\{v_1,v_2,\dots ,v_t\}\text{is an independent set in }H\}$ and let $U_t\left(H\right)=min\left\{\right|{?}_{i=1}^t{N}_H\left(v_i\right)\left|\right|\{v_1,v_2,?,v_t\}\text{is an independent set in }H\}$. We show that for a given number $?$ and given integers $p\ge t>0$, $k\in \{2,3\}$ and $N=N(p,?)$, if $H$ is a $k$-connected claw-free graph of order $n>N$ with $\delta \left(H\right)\ge 3$ and its Ryjác?ek’s closure $cl\left(H\right)=L\left(G\right)$, and if $d_t\left(H\right)\ge t(n+?)∕p$ where $d_t\left(H\right)\in \{{\sigma }_t\left(H\right),U_t\left(H\right)\}$, then either $H$ is Hamiltonian or $G$, the preimage of $L\left(G\right)$, can be contracted to a $k$-edge-connected $K_3$-free graph of order at most $max\{4p?5,2p+1\}$ and without spanning closed trails. As applications, we prove the following for such graphs $H$ of order $n$ with $n$ sufficiently large:(i) If $k=2$, $\delta \left(H\right)\ge 3$, and for a given $t$ ($1\le t\le 4$) $d_t\left(H\right)\ge \frac{tn}{4}$, then either $H$ is Hamiltonian or $cl\left(H\right)=L\left(G\right)$ where $G$ is a graph obtained from $K_{2,3}$ by replacing each of the degree 2 vertices by a $K_{1,s}$ ($s\ge 1$). When $t=4$ and $d_t\left(H\right)={\sigma }_4\left(H\right)$, this proves a conjecture in Frydrych (2001).(ii) If $k=3$, $\delta \left(H\right)\ge 24$, and for a given $t$ ($1\le t\le 10$) $d_t\left(H\right)>\frac{t(n+5)}{10}$, then $H$ is Hamiltonian. These bounds on $d_t\left(H\right)$ in (i) and (ii) are sharp. It unifies and improves several prior results on conditions involved ${\sigma }_t$ and $U_t$ for the hamiltonicity of claw-free graphs. Since the number of graphs of orders at most $max\{4p?5,2p+1\}$ are fixed for given $p$, improvements to (i) or (ii) by increasing the value of $p$ are possible with the help of a computer.     

Graphs with only caterpillars as spanning trees

A connected graph G is caterpillar-pure if each spanning tree of G is a caterpillar. The caterpillar-pure graphs are fully characterized. Loosely speaking they are strings or necklaces of so-called pearls, except for a number of small exceptional cases. An upper bound for the number of edges in terms of the order is given for caterpillar-pure graphs, and those which attain the upper bound are characterized.     

Spanning Trees with Few Leaves

In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k ≥ 2 and m ≥ 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n − k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win.     

Embedding nearly-spanning bounded degree trees

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1 − ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ≥ 2 and 0 < ε < 1, there exists a constant c = c(d, ε) such that a random graph G(n, c/n) contains almost surely a copy of every tree T on (1 − ε)n vertices with maximum degree at most d. We also prove that if an (n, D, λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λ in their absolute values) has large enough spectral gap D/λ as a function of d and ε, then G has a copy of every tree T as above. Research supported in part by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by a Wolfensohn fund and by the State of New Jersey. Research supported in part by USA-Israel BSF Grant 2002-133, and by grants 64/01 and 526/05 from the Israel Science Foundation. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

Degree sum conditions for the existence of homeomorphically irreducible spanning trees

In 1990, Albertson, Berman, Hutchinson, and Thomassen proved a theorem which gives a minimum degree condition for the existence of a spanning tree with no vertices of degree 2. Such a spanning tree is called a homeomorphically irreducible spanning tree (HIST). In this paper, we prove that every graph of order $n$ ($n\ge 8$) contains a HIST if $d(u)+d(v)\ge n?1$ for any nonadjacent vertices $u$ and $v$. The degree sum condition is best possible.