Spanning trees in hyperbolic graphs

We construct spanning trees in locally finite hyperbolic graphs that represent their hyperbolic compactification in a good way: so that the tree has at least one but at most a bounded number of disjoint rays to each boundary point. As a corollary we extend a result of Gromov which says that from every hyperbolic graph with bounded degrees one can construct a tree (disjoint from the graph) with a continuous surjection from the ends of the tree onto the hyperbolic boundary such that the surjection is finite-to-one. We shall construct a tree with these properties as a subgraph of the hyperbolic graph, which in addition is also a spanning tree of that graph.     

Spanning trees of extended graphs

A generalization of the Prüfer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs.     

Spanning trees with many leaves in cubic graphs

For a connected graph G let L(G) denote the maximum number of leaves in any spanning tree of G. We give a simple construction and a complete proof of a result of Storer that if G is a connected cubic graph on n vertices, then L(G) ? [(n/4) + 2], and this is best possible for all (even) n. The main idea is to count the number of “dead leaves” as the tree is being constructed. This method of amortized analysis is used to prove the new result that if G is also 3-connected, then L(G) ? [(n/3) + (4/3)], which is best possible for many n. This bound holds more generally for any connected cubic graph that contains no subgraph K₄ - e. The proof is rather elaborate since several reducible configurations need to be eliminated before proceeding with the many tricky cases in the construction.     

Spanning subgraphs with specified valencies

The author has published a necessary and sufficient condition for a finite looplesses graph to have a spanning subgraph with a specified positive valency at each vertex (see [8,9]). In the present paper it is contended that the condition can be made more useful as a tool of graph theory by imposing a maximality condition.     

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 subgraphs with specified valencies

The author has published a necessary and sufficient condition for a finite loopless graph to have a spanning subgraph with a specified positive valency at each vertex (see [8], [9]). In the present paper it is contended that the condition can be made more useful as a tool of graph theory by imposing a maximality condition.     

Spanning 3-ended trees in k-connected K 1,4-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.     

Embedding graphs in Cayley graphs

IfY is a finite graph then it is known that every sufficiently large groupG has a Cayley graph containing an induced subgraph isomorphic toY. This raises the question as to what is sufficiently large. Babai and Sós have used a probabilistic argument to show that |G| > 9.5 |Y|³ suffices. Using a form of greedy algorithm we strengthen this to (2 + \sqrt 3 )|Y|^3 $$ " align="middle" border="0"> . Some related results on finite and infinite groups are included.     

Cayley graphs with few automorphisms

Journal of Algebraic Combinatorics - We show that every finitely generated group G with an element of order at least $$bigl (5{{,mathrm{rank},}}(G)bigr )^{12}$$ admits a locally finite...     

Shifts in Cayley graphs

An automorphism of an undirected simple graph is called a shift if it maps every vertex to an adjacent one. For all finite groups G, we determine the minimum nonzero valency of a Cayley graph on G that does not admit a shift. We also get a classification of groups with all involutions central and such that for every pair a,b of elements of the group, one of ab=ba, aba⁻¹=b⁻¹, bab⁻¹=a⁻¹ or a²=b^±2 holds.     

Spanning trees with bounded degrees

Lets andk be positive integers. We prove that ifG is ak-connected graph containing no independent set withks+2 vertices thenG has a spanning tree with maximum degree at mosts+1. Moreover ifs3 and the independence number (G) is such that (G)1+k(s–1)+c for some0ck thenG has a spanning tree with no more thanc vertices of degrees+1.     

Spanning trees with many leaves

Let a maximal chain of vertices of degree 2 in a graph G consist of k > 0 vertices. We prove that G has a spanning tree with more than \fracv(G)2k + 4 \frac{{v(G)}}{{2k + 4}} leaves (where υ(G) is the number of vertices of the graph G). We present an infinite series of examples showing that the constant \frac12k + 4 \frac{1}{{2k + 4}} cannot be enlarged. Bibliography: 7 titles.     

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.     

Spanning trees with pairwise nonadjacent endvertices

A spanning tree of a connected graph G is said to be an independency tree if all its endvertices are pairwise nonadjacent in G. We prove that a connected graph G has no independency tree if and only if G is a cycle, a complete graph or a complete bipartite graph the color classes of which have equal cardinality.     

Hamiltonian circuits in Cayley graphs

The following result is proved: If either G is a finite abelian group or a semidirect product of a cyclic group of prime order by a finite abelian group of odd order, then every connected Cayley graph of G is hamiltonian.     

Hamiltonian paths in Cayley graphs

The classical question raised by Lovász asks whether every Cayley graph is Hamiltonian. We present a short survey of various results in that direction and make some additional observations. In particular, we prove that every finite group G has a generating set of size at most log₂|G|, such that the corresponding Cayley graph contains a Hamiltonian cycle. We also present an explicit construction of 3-regular Hamiltonian expanders.     

Vertex reconstruction in Cayley graphs

In this survey paper we review recent results on the vertex reconstruction problem (which is not related to Ulam’s problem) in Cayley graphs. The problem of reconstructing an arbitrary vertex x from its r-neighbors, that are, vertices at distance at most r from x, consists of finding the minimum restrictions on the number of r-neighbors when such a reconstruction is possible. We discuss general results for simple, regular and Cayley graphs. To solve this problem for given Cayley graphs, it is essential to investigate their structural and combinatorial properties. We present such properties for Cayley graphs on the symmetric group and the hyperoctahedral group (the group of signed permutations) and overview the main results for them. The choice of generating sets for these graphs is motivated by applications in coding theory, computer science, molecular biology and physics.