Spanning k-ended trees of 3-regular connected graphs

Hamed Ghasemian Zoeram, Daniel Yaqubi

Faculty of Agriculture and Animal Science, University of Torbat-e Jam, Iran

hamed90ghasemian@gmail.com, daniel yaqubi@yahoo.es

A vertex of degree one is called an end-vertex and the set of end-vertices of G is denoted by End(G). For a positive integer k, a tree T be called k-ended tree if |End(T)| ≤ k. In this paper, we obtain sufficient conditions for spanning k-trees of 3-regular connected graphs. We give a construction sequence of graphs satisfying the condition. At the end, we present a conjecture about spanning k-ended trees of 3-regular connected graphs.

Keywords: Spanning tree, k-ended tree, leaf, 3-regular graph, connected graph Mathematics Subject Classification : 05C05, 05C07

DOI:10.5614/ejgta.2017.5.2.4

1. Introduction

Throughout this article we consider only finite undirected labeled graphs without loops or multiple edges. The vertex set and edge set of graph G is denoted by V = V (G) and E = E(G), respectively. For u, v ∈ V , an edge joining two vertices u and v is denoted by uv or vu. The neighbourhood NG(v) or N(v) of vertex v is the set of all u ∈ V which are adjacent to v. The degree of a vertex v, denoted by degG(u) = |NG(v)|.

The minimum degree of a graph G is denoted δ(G) and the maximum degree is denoted ∆(G). If all vertices of G have same degree k, then the graph G is called k-regular. The distance between vertices u and v, denoted by dG(u, v) or d(u, v), is the length of a shortest path between u and v. A Hamiltonian path of a graph is a path passing through all vertices of the graph. A graph is

Received: 20 March 2016, Revised: 30 July 2017, Accepted: 14 August 2017.

Hamiltonian-connected if every two vertices are connected with a Hamiltonian path. In graph G, an independent set is a subset S of V (G) such that no two vertices in S are adjacent. A maximum independent set is an independent set of largest possible size for a given graph G. This size is called the independence number of G, that denoted by α(G).

A vertex of degree one is called an end-vertex, and the set of end-vertices of G is denoted by End(G). If T is a tree, an end-vertex of a T is usually called a leaf of T and the set of leaves of T is denoted by leaf(T). A spanning tree is called independence if End(G) is independent in G. For a positive integer k, a tree T is said to be a k-ended tree if |End(T)| ≤ k. We define σk(G) = min{d(v1) + . . . + d(vk) | {v1, . . . , vk} is an independent set in G}. Clearly, σ1(G) = δ(G).

By using σ2(G), Ore [4] obtain the following famous theorem on Hamiltonian path. Notice that a Hamiltonian path is spanning 2-ended tree. A Hamilton cycle can be interpreted as a spanning 1-ended tree. In particular, K² is hamiltonian and is a 1-ended tree.

Theorem 1.1. [4] Let G be a connected graph, if σ2(G) ≥ |G| − 1, then G has Hamiltonian path.

The following theorem of Las Vergnas Broersma and Tuinstra [1] gives a similar sufficient condition for a graph G to have a spanning k-ended tree.

Theorem 1.2. [2] Let k ≥ 2 be an integer, and let G be a connected graph. If σ2(G) ≥ |G|−k+1, then G has a spanning k-ended tree.

Win [10] obtained a sufficient condition related to independent number for k-connected graph that confirms a conjecture of Las Vergnas Broersma and Tuinstra [1] gave a degree sum condition for a spanning k-ended tree.

Theorem 1.3. [10] Let k ≥ 2 and let G be a m-connected graph. If α(G) ≤ m + k − 1, then G has a spanning k-ended tree.

A closure operation is useful in the study of existence of Hamiltonian cycles, Hamiltonian path and other spanning subgraphs in graph. It was first introduced by Bondy and Chavatal.

Theorem 1.4. [1] Let G be a graph and let u and v be two nonadjacent vertices of G then,

• (1) Suppose degG(u) + degG(v) ≥ |G|. Then G has a Hamiltonian cycle if and only if G + uv has a Hamiltonian cycle.
• (2) Suppose degG(u) + degG(v) ≥ |G| − 1. Then G has a Hamiltonian path if and only if G + uv has a Hamiltonian path.

After [1], many researchers have defined other closure concepts for various graph properties. More on k-ended tree and spanning tree can be found in [6, 7, 8, 9]. In this paper, we obtain sufficient conditions for spanning k-ended trees of 3-regular connected graphs and with construction sequence of graphs like Gm, we will show this condition is sharp. At the end, we present a conjecture about spanning k-ended trees of 3-regular connected graphs.

2. Our results

Lemma 2.1. Let T be a tree with n vertices such that ∆(T) ≤ 3. If |leaf(T)| = k and p be the number of vertices of degree 3 in T, then k = p + 2.

Proof. It is easy by the induction on p.

Lemma 2.2. Let G be a labelled graph and k ≥ 3 be the smallest integer such that G has a spanning tree T with k leaves. Then, no two leaves of T are adjacent in G.

Proof. Put S = {v1, v2, . . . , vk} be the set of all leaves of T. By contradiction, suppose that v¹ and v² are adjacent vertices in G. If T¹ = T + v1v2, then T¹ contains a unique cycle as C : v1v2c1c² . . . c`v<sup>1</sup> where c<sup>i</sup> ∈ G for 1 ≤ i ≤ `. Since k ≥ 3 then there exist vertex v^s ∈ G such that it is not a vertex of C. Let P be the shortest path of vertex v^s to the cycle C such that its intersection with cycle C is c^j for 1 ≤ j ≤ `.

Now, we omit the edge cj−1c^j of T1, (If j = 1 put cj−¹ = v2). Let T² = T¹ − cj−1c^j . Then T² is a spanning subtree of G such that deg^T2 (c^j ) ≥ 2. The vertices of degree one in spanning subtree T² is equal to the set {v3, v4, . . . , vk} either {v3, v4, . . . , vk, cj−1} . That is a contradiction by minimality of k.

Theorem 2.1. Let G be a labeled 3-regular connected graph such that |V (G)| = n ≥ 6. Then G has a spanning n+2 4 -ended tree.

Proof. For the graph T, we denote the vertices of degree 1 with the set A1, the vertices of degree 2 with the set A² and the vertices of degree 3 with the set A3.

If v ∈ A³ then the two adjacent edges to v (those were in G but are not in T), each one connects v to a vertex of A² in G, because by Lemma 2.2 it can not connect v to a member of A1. So, for each vertex in A¹ there exist two vertices in A² such that they are connected to v in G but not in T. Now, we have 2 × |A1| ≤ |A2|. Let |A1| = k, |A2| = s and |A3| = p. By Lemma 2.1 we have k = p + 2 and since 2|A1| ≤ |A2| then 2k ≤ s.

We have

\[n=p+s+k=k-2+s+k\geq k-2+2k+k=4k-2,\] Then \(k\leq \lfloor \frac{n+2}{4}\rfloor.\)

3. Some concluding remarks

Now we construct the sequence G^m of 3-regular graphs, For m = 1, Consider the graph G¹ as Figure 1.

Clearly G¹ has spanning subtree like T that has 3 leaves and G has no spanning subtree with less than 3 leaves. Every part of G¹ like subgraph induced by vertices {1, 2, 3, 4, 5} is called a branch, so G¹ has 3 branch. Let H be a branch of G¹ with vertices {1, 2, 3, 4, 5} and set of edges {12, 15, 23, 24, 34, 35, 45}. Since the edge {01} is a cut edge in G1, So T must has a vertex with degree one in H. Also in every other branches of G1, T must has a vertex with degree one. so G¹ is 3-ended tree and has no spanning tree with less than 3 leaves. Now, we counteract 3-regular graph

Figure 1. The 3-regular graph \(G_1\) with 3 branch.

Figure 2. One part of \(G_2\) constructed from \(G_1\).

\(G_2\), consider \(G_1\) and for each branch of that like H defined as above, we removed two vertices \(\{3,4\}\) and add 8 new vertices \(\{v_1,\ldots,v_8\}\) then we construct new 3-regular graph as Figure 2.

Clearly \(|G_2| = 16 + 3 \times 6\) and minimum number leaves in every spanning subtree of \(G_2\) is at least \(2 \times 3\) and obviously \(G_2\) has spanning subtree with \(2 \times 3\) leaves.

Let the number of vertices of \(G_m\) is equal n and the number of branches of \(G_m\) is equal k, then we have the table 1.

Table 1. The number of vertices and branches of \(G_m\) for \(m \in \mathbb{N}\).

It obvious for each \(m \in \mathbb{N}\) if the number of vertices of \(G_m\) is equal n and the number of branches of \(G_m\) is equal k, then \(\frac{n+2}{6} = k\), and so \(G_m\) is \(\frac{n+2}{6}\)-ended tree (such that \(\frac{n+2}{6}\) is the minimum number for that \(G_m\) is \(\frac{n+2}{6}\)-ended tree).

Conjecture 1. There exists n ∈ N such that each 3-regular graph with at least n vertices has a spanning b n+2 6 c-ended tree.

References

• [1] J.A. Bondy, and V. Chvatal, A method in graph theory, ´ Discrete Math. 15 (2) (1976), 111– 135.
• [2] H. Broersma and H. Tuinstra, Independence trees and Hamilton cycles, J. Graph Theory 29 (1998), 227–237.
• [3] M. Kano, A. Kyaw, H. Matsuda, K. Ozeki, A. Saito and T. Yamashita, Spanning trees with a bounded number of leaves in a claw-free graph, submitted.
• [4] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), 55.
• [5] M. Las Vergnas, Sur une proprit des arbres maximaux dans un graphe, C. R. Acad. Sci. Paris Sr. A 272 (1971), 1297–1300.
• [6] J. Akiyama and M. Kano, Factors and factorizations of graphs, Lecture Note in Mathematics (LNM 2031), Springer, 2011 (Chapter 8).
• [7] A. Czygrinow, G. Fan, G. Hurlbert, H.A. Kierstead and W.T. Trotter, Spanning trees of bounded degree, Electron. J. Combin. 8 (1) (2001) 12. R33.
• [8] K. Ozeki and T. Yamashita, Spanning trees: a survey, Graphs Combin. 27 (2011), 1–26.
• [9] G. Salamon and G. Wiener, On finding spanning trees with few leaves, Inform. Process. Lett. 105 (2008), 164–169.
• [10] S. Win, On a conjecture of Las Vergnas concerning certain spanning trees in graphs, Result. Math. 2 (1979), 215–224.