Some New Results On Structures Of Subgraphs And Graph Parameters Concerning Degree Sums

Investigating degree sums and structures of subgraphs originated from Dirac in 1952 who studied the well known hamiltonian problems.It states that any graph with a large degree sums will necessarily contain an orderly substructure.The study of de-gree sums and structures of subgraphs involves many fields such as hamiltonian graph theory,graph coloring theory,extremal graph theory,etc.The main power,driving this field forward,is hamiltonian graph theory.It supplies us with new methods and new problems continuously,which make hamiltonian graph theory become one of the fundamental fields of graph theory and plays a central role in the field of degree sums and substructures.Various researchers have made a lot of efforts and contributions to the area of degree sums and substructures including N.Alon,J.Bondy,P.Erdos,G.Fan,O.Ore,etc.Structure analysis,probabilistic methods and so on provide powerful analysis tools to attack problems on this field.Hamiltonian graph theory has evolved into a great family of many streams includ-ing hamiltonicity such as various cycle substructures,traceability such as special trees,etc.Graph coloring theory is a traditional field with many classes of colorings such as edge coloring,vertex coloring and some other colorings with additional restricts or re-laxations on these colorings.The extremal problems of graph parameters is a direction of extremal graph theory.In this thesis,first we focus on degree sums and structures of subgraphs,including dominating cycle and spanning trees with bounded branch ver-tices which are hamiltonian graph theory problems,and a natural relaxation of typical edge coloring which are graph coloring theory problems.Then we consider problems of extremal graph parameters involved distance.In chapter 1,we first introduce some related useful basic concepts and definitions.Then we provide a relative introduction to the background,known results and new results we obtained of the researches in this thesis.For an integer k? 2,define?k(G)=min{?i=1k d(xi)| {X1,…,xk} is an independent set of G}.1.Dominating CyclesA cycle C of G is dominating if any vertex of V(G)\V(C)has at least one neigh-bor in C and V(G)\V(C)is an independent set.In chapter 2,we focus on the problem of degree sums and that every longest cycle of a graph is dominating.Actually,if diff(G)=p(G)-c(G)?1,then every longest cycle is dominating.In 2007,Liu et al.[Graphs and Combinatorics,23(2007),433-443]posed the following conjecture.Conjecture 1.Let G be a k-connected graph on n vertices with k?2.If ?k+1(G)>(k+1)(n+1)/3,then diff(G)?.Conjecture 1 is true for k=2,3,which were showed by Enomoto et al.[Jour-nal of Graph Theory,20(1995),213-225]and Liu et al.[Graphs and Combinatorics,23(2007),433-443],independently.It is still open for k?4.The methods taken by showing k=2,3 is to find an expected independent set on a longest path,while it is hard to generalizes this technique on k-connected graphs for k?4.On the other hand,since diff(G)?1 is rigorous,few results about diff(G)?1 are known.Thus,Conjecture 1 is much difficult to break through.Hence,we posed the following.Problem 1.Let G be a k-connected graph on n vertices with k?2.If ?k+1(G)>(k+1)(n+1)/3,then every longest cycle is dominating?If the answer of Problem 1 is negative,then it would negate Conjecture 1,other-wise it would take some support to Conjecture 1.In fact,Problem 1 is still open for k?4.In 1980,a classical result of Bondy implies that Problem 1 is true for k=2.Theorem A.Let G be a 2-connected graph on n vertices.If ?3(G)>n+1,then every longest cycle is dominating.A result of Lu et al.[Journal of Graph Theory,49(2005),135-150]shows that Problem 1 is true for k=3.Theorem B.Let G be a 3-connected graph on n vertices.If ?4(G)>(4n+4)/3,then every longest cycle is dominating.In chapter 2,based on the interest in Problem 1 and inspired by Theorem B,our answer of this problem is affirmative.It is worth noting that the techniques of extend-ing cycle and estimating three types degree sums of independent sets of cardinality 3 approached by Lu et al.can be improved and then popularized.We solved this problem by elaborately developing the techniques of extending cycle in k-connected non-hamiltonian graphs to find a set of noninsertible vertices and estimate four types degree sums of independents of cardinality 3.Our main result is the following.Theorem 1.Let G be a k-connected graph of order n with k? 2.If ?k+1(G)>(k+1)(n+1)/3,then every longest cycle is dominating.The lower bound of ?k+1(G)in Theorem 1 is tight.Obviously,taking k=2,3 in Theorem 1,we have Theorem A and Theorem B,respectively.On the other hand,it seems that Theorem 1 provides some supports for the truth of Conjecture 1.2.Spanning BroomsIn chapter 3,we focus on degree sums and spanning trees with bounded branch vertices.A branch vertex in a tree is a vertex of degree greater than two.The existence of spanning trees with bounded branch vertices is a generalization of traceability in graph theory.Unfortunately,it is an NP-hard problem.A broom is a tree obtained from a star and a path by identifying an endpoint of a path to the center of the star.Al-though a broom contains at most one branch vertex,deciding whether a graph contains a spanning broom is an NP-complete problem.Therefore,looking for some sufficient conditions such that graphs having spanning trees with bounded branch vertices is the only plausible way to approach this problem.Chen et al.[Journal of Graph Theory,77(2014),237-250]posed the following conjecture.Conjecture 2.Let G be a connected graph of order n?3.If ?(G)? n-2,then G contains a spanning broom.In chapter 3,by using some important results of hamiltonian graph theory skill-fully and degree sums condition a3(G)? n-2 elaborately,we confirmed Conjecture 2 for n>50.Moreover,we showed the lower bound of ?3(G)is sharp by constructing a class of graphs.Our main result is as below.Theorem 2.Let G be a connected graph of order n>50.If a3(G)? n-2,then G contains a spanning broom.3.Proper Connection NumberIn chapter 4,we consider problems on degree sums and graphs with proper con-nection number 2.An edge-colored graph G is called properly connected if any two vertices u,v?(G)are connected by a properly colored(u,v)-path.The proper con-nection number pc(G)is the smallest number of colors needed to color G such that it is properly connected.A graph G is k-strong if there is a k-edge-coloring c of G such that there exist two properly colored(u,v)-paths P=uxx…xkv and P'=uy1…ylv with c(ux1)?c(uy1)and c(vxk)?c(vyl)for any two vertices u,v?V(G).Borozan et al.[Discrete Mathematics,312(2012),2550-2560]conjectured that if?(G)?3 for any 2-connected graph G,then pc(G)=2.Although this conjecture was proved to be wrong independently by Brause et al.[Graphs and Combinatorics,33(2017),833-843]and Huang et al.[Discrete Mathematics,340(2017),2217-2222],it supplies us with ideas to investigate which graphs of 2-connected are with pc(G)=2.Let ?(n)denote the minimum value such that pc(G)=2 for any 2-connected incomplete graph G of order n with ?(G)? ?(n).An interesting problem is:what's the exact value of ?(n)?Brause et al.settled the lower and upper bounds on ?(n)by constructing a counterexample and showing a theorem,respectively.Theorem C.n/42<?(n)?(n+28)/20.For connected graphs,Borozan et al.established a sharp lower bound on min-imum degree for a connected graph G having pc(G)=2:if ?(G)? |G|/4,then pc(G)=2.Chang et al.[Ars Combinatoria,145(2019),161-171]extended this result by a relaxation on degree condition.Theorem D.Let G be a connected graph of order n>9 with G?Kn.If ?2(G)?n/2,then pc(G)? 2.In chapter 4,inspired by the counterexamples constructed by Brause et al.and Huang et al.,we first constructed a class of graphs with proper connection number greater than 2 and one of which is with minimum degree n/36,which improves the lower bound of Theorem C.Our main result is as below.Theorem 3.?(n)>n/36.Secondly,based on Chvatal and Erdos Theorem,we further extended the scope of connected graphs which are with proper connection number 2 by a natural relax-ation on ?2(G)condition and the main result is as follows.Here,we excluded R1,3 connected graphs,each of which is with proper connection number greater than 2.A connected graph G is called R1,2 if |Bv|? 3 for some cut vertex v of G,where Bv={B:B is a block of G,v?V(B),|B+?3}.Otherwise,G is a R1,3-free graph.Our main idea is to partition the graph into a few induced subgraphs,by using the 2-strong property of one such subgraphs and joining them together to obtain a spanning subgraph R of G with pc(R)?2.Theorem 4.Let G be a R1,3-free connected graph of order n>48 with G?Kn.If?3(G)?3n/4,then pc(G)=2.4.Eccentric Connectivity IndexIn chapter 5,we consider extremal problems on eccentric connectivity index of graphs.Let ?(v)=max{d(u,v)|u?V(G)} denote the eccentricity of v.The eccen-tric connectivity index of G,denoted by ?c(G),is defined as#12where ?(uv)=?(u)+?(v)is called the weight of the edge uv.The eccentric connectivity index has been evaluated for some classes of graphs.Zhou and Du[MATCH.Communications in Mathematical and in Computer Chem-istry,63(2010),181-198],and independently,Morgan et al.[Discrete Mathematics,311(2011)1229-1234]showed that star is the unique graph obtained the minimum ec-centric connectivity index of connected graphs of order n,and the sharp upper bound for any tree Tn is attained by path.In the same paper,Zhou and Du established the sharp lower bound for unicyclic graphs on n vertices.The following Theorems 5-8 are our main results in chapter 5.Our first result is to establish the lower bound in terms of the order and the minimum degree of a graph G by using the fact that ?(v)? 2 for v?EV(G)if ?(G)?n-2,and if ?(G)=n-1,?(v)=1 for d(v)=?(G)and ?(u)=2 for d(u)<?(G),which improves the lower bound of connected graphs.Theorem 5.Let G be a connected graph of order n? 2?2-2?+4 with ?(G)=?.Then ?c(G)?(2?+1)n-2?-1 for ? is odd or ? is even and n is odd with equality if and only if ?(G)=(n-1,?,?,…,?),and ?c(G)?(2?+1)n-?+1 for ? is even and n is even with equality if and only if ?(G)=(n-1,?+1,?,…,?).Our second result is to establish the lower and upper bounds of ?c(Tn)for Tn with given degree sequence by using graph transformations reasonably.Theorem 6.Among n-vertex trees with nonincreasing degree sequence(d1,d2,…,dn),the greedy caterpillars obtain the maximum eccentric connectivity index.Theorem 7.Among n-vertex trees with nonincreasing degree sequence(d1,d2,…,dn),the greedy tree minimizes the eccentric connectivity index.Our final result is to establish the sharp lower bound for a unicyclic graph in terms of its order and radius,which extends the result of unicyclic.Our main idea is to apply the formula ?c(G)=?uv?E(G)?(uv)and estimate the weight of each edge by analyzing structures of G.Theorem 8.Let G be an n-vertex unicyclic graph with radius rad(G)? r? 2.(?)If 2r?n<2r+1,then ?c(G)? 2nr with equality if and only if G(?)Cn.(?)If n?2r+2,then ?c(G)?2rn+n-2r+2 for n ?3r-2 with equality if and only if G(?)U2rn,and ?c(G)?2rn+n-2r+1 for n?3r-1 with equality if and only if G ?y2r-1.