Constructing a spanning tree with many leaves

It was shown by Griggs and Wu that a graph of minimal degree 4 on n vertices has a spanning tree with at least \frac25 \frac{2}{5} n leaves, which is asymptomatically the best possible bound for this class of graphs. In this paper, we present a polynomial time algorithm that finds in any graph with k vertices of degree greater than or equal to 4 and k′ vertices of degree 3 a spanning tree with [ \frac25 ·k + \frac215 ·k￠ ] \left[ {\frac{2}{5} \cdot k + \frac{2}{{15}} \cdot k'} \right] leaves.     

On the “largeur d'arborescence”

Let la(G) be the invariant introduced by Colin de Verdière [J. Comb. Theory, Ser. B., 74:121–146, 1998], which is defined as the smallest integer n≥0 such that G is isomorphic to a minor of K_n×T, where K_n is a complete graph on n vertices and where T is an arbitrary tree. In this paper, we give an alternative definition of la(G), which is more in terms of the tree‐width of a graph. We give the collection of minimal forbidden minors for the class of graphs G with la(G)≤k, for k=2, 3. We show how this work on la(G) can be used to get a forbidden minor characterization of the graphs with (G)≤3. Here, (G) is another graph parameter introduced in the above cited paper. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 24–52, 2002     

On lower bounds for the chromatic number in terms of vertex degree

In this paper we discuss the existence of lower bounds for the chromatic number of graphs in terms of the average degree or the coloring number of graphs. We obtain a lower bound for the chromatic number of K_1,t-free graphs in terms of the maximum degree and show that the bound is tight. For any tree T, we obtain a lower bound for the chromatic number of any K_2,t-free and T-free graph in terms of its average degree. This answers affirmatively a modified version of Problem 4.3 in [T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley, New York, 1995]. More generally, we discuss δ-bounded families of graphs and then we obtain a necessary and sufficient condition for a family of graphs to be a δ-bounded family in terms of its induced bipartite Turán number. Our last bound is in terms of forbidden induced even cycles in graphs; it extends a result in [S.E. Markossian, G.S. Gasparian, B.A. Reed, β-perfect graphs, J. Combin. Theory Ser. B 67 (1996) 1–11].     

A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees

Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low-weight spanning tree such that the degree of each vertex is at most its specified bound is considered. In particular, modifying a given spanning treeTusingadoptionsto meet the degree constraints is considered. A novel network-flow-based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previous algorithm. If the degree constraintd(v) for eachvis at least 2, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times 2 − min{(d(v) − 2)/(deg_T(v) − 2) : deg_T(v) > 2}, where deg_T(v) is the initial degree ofv. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds foranyalgorithm at all, then it also holds for the given algorithm. Examples are provided in which no lighter tree meeting the degree constraint exists. Linear-time algorithms are provided with the same worst-case performance guarantee. ChoosingTto be a minimum spanning tree yields approximation algorithms with factors less than 2 for the general problem on geometric graphs with distances induced by variousL_pnorms. Finally, examples of Euclidean graphs are provided in which the ratio of the lengths of an optimal Traveling Salesman path and a minimum spanning tree can be arbitrarily close to 2.     

The spanning trees forced by the path and the star

A set S of trees of order n forces a tree T if every graph having each tree in S as a spanning tree must also have T as a spanning tree. A spanning tree forcing set for order n that forces every tree of order n. A spanning-tree forcing set S is a test set for panarboreal graphs, since a graph of order n is panarboreal if and only if it has all of the trees in S as spanning trees. For each positive integer n ≠ 1, the star belongs to every spanning tree forcing set for order n. The main results of this paper are a proof that the path belongs to every spanning-tree forcing set for each order n ∉ {1, 6, 7, 8} and a computationally tractable characterization of the trees of order n ≥ 15 forced by the path and the star. Corollaries of those results include a construction of many trees that do not belong to any minimal spanning tree forcing set for orders n ≥ 15 and a proof that the following related decision problem is NP-complete: an instance is a pair (G, T) consisting of a graph G of order n and maximum degree n - 1 with a hamiltonian path, and a tree T of order n; the problem is to determine whether T is a spanning tree of G. © 1996 John Wiley & Sons, Inc.     

Metric characterizations of proper interval graphs and tree-clique graphs

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When T is a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real line such that no interval contains another. We present here metric characterizations of proper interval graphs and extend them to tree-clique graphs. This is done by demonstrating “local” properties of tree-clique graphs with respect to the subgraphs induced by paths of a compatible tree. © 1996 John Wiley & Sons, Inc.     

Removable edges in cyclically 4-edge-connected cubic graphs

We consider various ways of obtaining smaller cyclically 4-edge-connected cubic graphs from a given such graph. In particular, we consider removable edges: an edgee of a cyclically 4-edge-connected cubic graphG is said to be removable ifG is also cyclically 4-edge-connected, whereG is the cubic graph obtained fromG by deletinge and suppressing the two vertices of degree 2 created by the deletion. We prove that any cyclically 4-edge-connected cubic graphG with at least 12 vertices has at least 1/5(|E(G)| + 12) removable edges, and we characterize the graphs with exactly 1/5(|E(G)| + 12) removable edges.This work was carried out while the first author held a Niels Bohr Fellowship from the Royal Danish Academy of Sciences.     

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} .     

图的度和与扩路

本文讨论了两顶点的度和与路可扩之间的关系,得到了如下结果:设G是n阶图,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+n/k(2≤k≤n-2),则G中任意一个满足k+1≤|P|相似文献   

Dense trees: a new look at degenerate graphs

Dense trees are undirected graphs defined as natural extensions of trees. They are already known in the realm of graph coloring under the name of k-degenerate graphs. For a given integer k1, a k-dense cycle is a connected graph, where the degree of each vertex is greater than k. A k-dense forest F=(V,E) is a graph without k-dense cycles as subgraphs. If F is connected, then is a k-dense tree. 1-dense trees are standard trees. We have |E|k|V|−k(k+1)/2. If equality holds F is connected and is called a maximal k-dense tree. k-trees (a subfamily of triangulated graphs) are special cases of maximal k-dense trees.We review the basic theory of dense trees in the family of graphs and show their relation with k-trees. Vertex and edge connectivity is thoroughly investigated, and the role of maximal k-dense trees as “reinforced” spanning trees of arbitrary graphs is presented. Then it is shown how a k-dense forest or tree can be decomposed into a set of standard spanning trees connected through a common “root” of k vertices. All sections include efficient construction algorithms. Applications of k-dense trees in the fields of distributed systems and data structures are finally indicated.     

Dirac's Condition for Completely Independent Spanning Trees

Two spanning trees T₁ and T₂ of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T₁ and T₂ are internally disjoint. In this article, we show two sufficient conditions for the existence of completely independent spanning trees. First, we show that a graph of n vertices has two completely independent spanning trees if the minimum degree of the graph is at least . Then, we prove that the square of a 2‐connected graph has two completely independent spanning trees. These conditions are known to be sufficient conditions for Hamiltonian graphs.     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

Graphs with homeomorphically irreducible spanning trees

It is an NP-complete problem to decide whether a graph contains a spanning tree with no vertex of degree 2. We show that these homeomorphically irreducible spanning trees are contained in all graphs with minimum degree at least c√n and in triangulations of the plane. They are nearly present in all graphs of diameter 2. They do not necessarily occur in r-regular or r-connected graphs.     

A randomized embedding algorithm for trees

In this paper, we propose a simple and natural randomized algorithm to embed a tree T in a given graph G. The algorithm can be viewed as a “self-avoiding tree-indexed random walk“. The order of the tree T can be as large as a constant fraction of the order of the graph G, and the maximum degree of T can be close to the minimum degree of G. We show that our algorithm works in a variety of interesting settings. For example, we prove that any graph of minimum degree d without 4-cycles contains every tree of order εd ² and maximum degree at most d-2εd-2. As there exist d-regular graphs without 4-cycles and with O(d ²) vertices, this result is optimal up to constant factors. We prove similar nearly tight results for graphs of given girth and graphs with no complete bipartite subgraph K _s,t .     

On p-intersection representations

For a graph G = (V,E) and integer p, a p-intersection representation is a family F = {S_x: × E V} of subsets of a set S with the property that |S_u ∩ S_ν| ≥ p ∩ {u, ν} E E. It is conjectured in [1] that θ_p(G) ≤ θ (K_n/2,n/2) (1 + o(1)) holds for any graph with n vertices. This is known to be true for p = 1 by [4]. In [1], θ (K_n/2,n/2) ≥ (n² + (2p− 1n)n)/4p is proved for any n and p. Here, we show that this is asymptotically best possible. Further, we provide a bound on θp(G) for all graphs with bounded degree. In particular, we prove θp(G) ≤ O(n^1/p) for any graph Gwith the maximum degree bounded by a constant. Finally, we also investigate the value of θ_p for trees. Improving on an earlier result of M. Jacobson, A. Kézdy, and D. West, (The 2-intersection number of paths and bounded-degree trees, preprint), we show that θ₂(T) ≤ O(d√n) for any tree T with maximum-degree d and θ₂(T) ≤ O(n^3/4) for any tree on n vertices. We conjecture that our results can be further improved and that θ₂(T) ≤ O(d√n) as long as Δ(T) ≤ √n. If this conjecture is true, our method gives θ₂(T) ≤ O(n^3/4) for any tree T which would be the best possible. © 1996 John Wiley & Sons, Inc.     

Is every cycle basis fundamental?

A collection of (simple) cycles in a graph is called fundamental if they form a basis for the cycle space and if they can be ordered such that C_j(C₁ U … U C_j-1) ≠ Ø for all j. We characterize by excluded minors those graphs for which every cycle basis is fundamental. We also give a constructive characterization that leads to a (polynomial) algorithm for recognizing these graphs. In addition, this algorithm can be used to determine if a graph has a cycle basis that covers every edge two or more times. An equivalent dual characterization for the cutset space is also given.     

An improvement of fraisse's sufficient condition for hamiltonian graphs

Let G be a k-connected graph of order n. For an independent set c, let d(S) be the number of vertices adjacent to at least one vertex of S and > let i(S) be the number of vertices adjacent to at least |S| vertices of S. We prove that if there exists some s, 1 ≤ s ≤ k, such that Σ_xiEX d(X\{X_i}) > s(n?1) – k[s/2] – i(X)[(s?1)/2] holds for every independetn set X ={x₀, x₁ ?x_s} of s + 1 vertices, then G is hamiltonian. Several known results, including Fraisse's sufficient condition for hamiltonian graphs, are dervied as corollaries.     

Directed Graph Pattern Matching and Topological Embedding

Pattern matching in directed graphs is a natural extension of pattern matching in trees and has many applications to different areas. In this paper, we study several pattern matching problems in ordered labeled directed graphs. For the rooted directed graph pattern matching problem, we present an efficient algorithm which, given a pattern graphPand a target graphT, runs in time and spaceO(|E_P| |V_T| + |E_T|). It is faster than the best known method by a factor ofmin{|E_T|, |E_P| |V_T|}. This algorithm can also solve the directed graph pattern matching problem without increasing time or space complexity. Our solution to this problem outperforms the best existing method by Katzenelson, Pinter and Schenfeld by a factor ofmin{|V_P| |E_T|, |V_P| |E_P| |V_T|}. We also present an algorithm for the directed graph topological embedding problem which runs in timeO(|V_P| |E_T| + |E_P|) and spaceO(|V_P| |V_T| + |E_P| + |E_T|). To our knowledge, this algorithm is the first one for this problem.     

Matching graphs

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M₁ and M₂ of M(G) are adjacent if and only if |M₁ − M₂| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998