Received 14 February 2016; accepted 19 April 2016; published 22 April 2016

ABSTRACT

A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and, respectively, denote the order of the largest component and number of components in. In this paper, we show that for a connected graph G, if for any cut-set, then G has a k-tree.

Keywords:

The Rupture Degree, k-Tree, Induced Graph

1. Introduction

Throughout this paper, We consider only finite undirected graphs without loops and multiple edges. A graph always means a simple connected graph with vertex set and edge set. Let denote the maximum degree of G, and denote the subgraph of G induced by a subset S of. We by denote the degree of a vertex v in a graph G and the neighbor vertex set of v. Further for a

nonempty subset S of, we put and.

A k-tree of a connected graph G is a spanning tree with maximum degree k. Clearly, if, it reduces to that of a Hamiltonian path in G. Since every tree with maximum degree has a -tree, thus here we doesn’t consider trees.

A nonempty set S of independent vertices of G is called a frame of G, if is connected for any. If then S is called a k-frame.

In [1] and [2] , Win, Aung and Kyaw gave the ore-type condition and Fan-type condition for k tree as fellows (Theorem A and B).

Theorem A. If for every independent set S of k vertices of graph G, then G has a k tree.

Theorem B. Let and suppose, either or is a complete

graph, then G has a k tree.

Further, Kyaw in [3] gave a stronger result for k tree as theorem C.

Theorem C. Let G be a connected graph and an integer. If for

every -frame S in G, then G has a k tree.

The rupture degree of a graph G is introduced in [4] , which is an important parameter for measuring the structure characteristics of the connected graph G and defined as

where and, respectively, denote the order of the largest component and the number of components in.

In this paper, we consider the rupture degree and existence of k-tree in a connected graph G and thus give a new sufficient condition for a graph to have k tree.

Any undefined terms can be found in the standard references on graph theory, including Bondy and Murty [5] .

2. Main Result

Let G be a connected graph and k an integrity with. Now, we by proving the following theorem to discuss the relationship between the rupture degree and existence of k-tree in graph G.

Theorem 1. Let G be a connected graph but not a tree. If for any cut-set, then G has a k-tree.

Let H be an induced subgraph of G and with maximal order among all subgraphs containing k-tree, and let A be a set adjacent to some vertices in G but not in. Clearly, if, then G has k-tree. Now, we suppose that for any cut-set and A is nonempty for connected graph G. We by finding a contradiction to prove the above theorem. Firstly, we prove the following claims.

Claim 1. Let T be a k-tree of H. Then for.

Proof. Let T be a k-tree of H, which has maximal order among all the induced subgraphs of G having a k-tree. On the contrary, suppose that if there exist some vertex such that, then H could be expanded by joining xy for a neighbor y of x which is not in H. This is contradictive to the maximality of H. Thus for any.

Let T be a k-tree of H and. Since, we suppose that are all components of.

Claim 2. If there exist an edge for, then and.

Proof. Suppose that (or) for (or). Since, we may obtain a new k-tree from T of H by deleting one of the edges joining x to components (or) from T and adding the edge in T. Clearly, we obtain another k-tree of H and in the latter k-tree, x has degree less than k. Then H could be expanded and this is contradictive to the maximality of H. So the conclusion holds.

Claim 3. Let T be a k-tree of H and M is subset of with degree k. Then M is non-empty and satisfies the following property: Let, , be the components of. If for some i and j with, the vertex of is adjacent in H to the vertex of, then and has degree k and.

Proof. Since A is nonempty and for every with, M is non-empty. By Claim 2, the property holds with because the way in which we have picked the vertices or which go into N. Clearly, be a subset of the set of vertices of T of degree k in T. At the same time, we find that a vertex v of T adjacent to a vertex in G but not in is in.

Let T be a k-tree of H with as many k degree vertices as possible and be subsets of with degree k as above. Suppose that is one component of. If is nonempty, we select and suppose that, , be the components of.

Claim 4. For m and n, with, if there exists a vertex of adjacent to a vertex of in H. Then and.

Proof. Suppose that (or) for (or). Since, we may obtain a new k-tree from T of H by deleting one of the edges joining to components (or) from T and adding the edge in T. Clearly, y has degree less than k in k-tree of H. Then combine we know this is contradictive to Claim 3. The conclusion holds.

By taking as the claims and let be maximal, then we obtain the follows claim as a straightforward consequence.

Claim 5. Let T be a k-tree of H with maximal number of k degree vertices. Then, there is no edge of H joining any components of.

Proof. Given our choice of T, M and N as above, we derive a contradiction by assuming that there is an edge yz of H with endpoints y and z joining two components of. If the path in T joining y and z contains a vertex of M, then by claim 3, either y or z is in N which is absurd. Then this path contains no vertex of M and y and z are therefore in the same component of for some i with. Now let w be a vertex of N on the path in T joining y and z and let, , be the components of. Now let be the set of all vertices of having property of claim 4. Further, let and. Since contains y or z, claim 2 holds with and replacing M and N, respectively. Moreover, is greater than. But this contradicts to our choice of and N. This shows that there is no edge in H joining any components of.

Now we are ready for the proof of theorem 2.1.

The proof of theorem 2.1. Since A is nonempty and thus H is an induced proper subgraph of G, we have. By claim 5 we know that. At the same time, we know that reaches minimum when is itself a tree. Thus we have

On the other hand, since for any cut-set we have

and,

This is a contradiction. Therefore A is empty and the proof is completed.

Acknowledgements

We thank the editor and the referee for their comments. Research of Qingning Wang and Xiaoling Wang is funded by the National Science Foundation grant 11561056. This support is greatly appreciated.

Cite this paper

Yinkui Li,Qingning Wang,Xiaoling Wang, (2016) The Rupture Degree of Graphs with k-Tree. Open Journal of Discrete Mathematics,06,105-107. doi: 10.4236/ojdm.2016.62011

References