On k-ordered Graphs Involved Degree Sum

Abstract A graph G is k-ordered Hamiltonian,2≤k≤n,if for every ordered sequence S of k distinctvertlces of G,there exists a Hamiltonian cycle that encounters S in the given order. In this article, we provethat if G is a graph on n vertices with degree sum of nonadjacent vertices at least n+3k-9/2,then G is k-orderedHamiltonian for k=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n+2[k/2]-2 ifk(G)≥3k-1/2 or δ(G)≥5k-4.Several known results are generalized.     

任意长圈覆盖指定的独立的点

An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define σ2（G） = ∞）. Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2（G） ≥ n ＋ k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that ｜Ci｜ ≤ s and vi ∈ V（Ci） for all 1 ≤ i ≤ k.
The condition of degree sum σs（G） ≥ n ＋ k - 1 is sharp.     

Hamiltonicity of 4-connected graphs

Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.     

和图、整和图与模和图的几个结果

Let N denote the set of positive integers. The sum graph G^＋（S） of a finite subset S belong to N is the graph （S, E） with uv ∈ E if and only if u ＋ v ∈ S. A graph G is said to be a sum graph if it is isomorphic to the sum graph of some S belong to N. By using the set Z of all integers instead of N, we obtain the definition of the integral sum graph. A graph G = （V, E） is a mod sum graph if there exists a positive integer z and a labelling, λ, of the vertices of G with distinct elements from {0, 1, 2,..., z - 1} so that uv ∈ E if and only if the sum, modulo z, of the labels assigned to u and v is the label of a vertex of G. In this paper, we prove that flower tree is integral sum graph. We prove that Dutch m-wind-mill （Dm） is integral sum graph and mod sum graph, and give the sum number of Dm.     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

The distance coloring of graphs

Let G be a connected graph with maximum degree Δ≥ 3.We investigate the upper bound for the chromatic number χγ(G) of the power graph Gγ.It was proved that χγ(G) ≤Δ(Δ-1)γ-1Δ-2+ 1 =:M + 1,where the equality holds if and only if G is a Moore graph.If G is not a Moore graph,and G satisfies one of the following conditions:(1) G is non-regular,(2) the girth g(G) ≤ 2γ- 1,(3)g(G) ≥ 2γ + 2,and the connectivity κ(G) ≥ 3 if γ≥ 3,κ(G) ≥ 4 but g(G) 6 if γ = 2,(4) Δis sufficiently larger than a given number only depending on γ,then χγ(G) ≤ M- 1.By means of the spectral radius λ1(G) of the adjacency matrix of G,it was shown that χ2(G) ≤λ1(G)2+ 1,where the equality holds if and only if G is a star or a Moore graph with diameter 2 and girth 5,and χγ(G)λ1(G)γ+1 ifγ≥3.     

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

On strong metric dimension of graphs and their complements

A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices S■V(G) is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim(G), is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n≥2, we characterize G such that sdim(G) equals 1, n-1, or n-2, respectively. We give a Nordhaus-Gaddum-type result for the strong metric dimension of a graph and its complement: for a graph G and its complement G, each of order n≥4 and connected, we show that 2≤sdim(G)+sdim(G)≤2( n-2). It is readily seen that sdim(G)+sdim(G)=2 if and only if n=4; we show that, when G is a tree or a unicyclic graph, sdim(G)+sdim(G)=2(n 2) if and only if n=5 and G ～=G ～=C5, the cycle on five vertices. For connected graphs G and G of order n≥5, we show that 3≤sdim(G)+sdim(G)≤2(n-3) if G is a tree; we also show that 4≤sdim(G)+sdim(G)≤2(n-3) if G is a unicyclic graph of order n≥6. Furthermore, we characterize graphs G satisfying sdim(G)+sdim(G)=2(n-3) when G is a tree or a unicyclic graph.     

Pancyclism and Bipancyclism of Hamiltonian Graphs

A graph G on n vertices is called pancyclic if it contains cycles of everylength k, for 3≤k≤n. A bipartite graph on 2n vertices is called bipancyclicif it contains cycles of every even length 2k, for 2≤k≤n. In this paper,we consider only finite, undirected graphs without loops ormultipie edges. We shall give a new sufficient condition ensuring a Hamiltonian graph tobe pancyclic(or bipancyclic), The main results are the following two theorems.Theorem A. Let G be a Hamiltonian graph of order n. If there exisis a     

An implicit degree ore-condition for pancyclicity of graphs

In 1989, Zhu, Li and Deng introduced the definition of implicit degree of a vertex v in a graph G, denoted by id(v). In this paper, we prove that if G is a 2-connected graph of order n such that id(u) + id(v) ≥ n for each pair of nonadjacent vertices u and v in G, then G is pancyclic unless G is bipartite, or else n = 4r, r ≥ 2 and G is isomorphic to F4r .     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

On a k-Tree Containing Specified Leaves in a Graph

A k-tree of a graph is a spanning tree with maximum degree at most k. We give sufficient conditions for a graph G to have a k-tree with specified leaves: Let k,s, and n be integers such that k≥2, 0≤s≤k, and n≥s+1. Suppose that (1) G is (s+1)-connected and the degree sum of any k independent vertices of G is at least |G|+(k−1)s−1, or (2) G is n-connected and the independence number of G is at most (n−s)(k−1)+1. Then for any s specified vertices of G, G has a k-tree containing them as leaves. We also discuss the sharpness of the results. This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement of Young Scientists, 15740077, 2005 This research was partially supported by the Japan Society for the Promotion of Science for Young Scientists.     

Graph powers and k-ordered Hamiltonicity

It is known that if G is a connected simple graph, then G³ is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v₁, v₂,…,v_k of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k?4, then G^⌊3k/2⌋-2 is k-ordered Hamiltonian for every connected graph G on at least k vertices. By considering the case of the path graph P_n, we show that this result is sharp. We also give a lower bound on the power of the cycle C_n that guarantees k-ordered Hamiltonicity.     

Degree conditions for k‐ordered hamiltonian graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003     

A vertex cover with chorded 4-cycles

Let k be an integer with k ≥ 2 and G a graph with order n > 4k. We prove that if the minimum degree sum of any two nonadjacent vertices is at least n + k, then G contains a vertex cover with exactly k components such that k−1 of them are chorded 4-cycles. The degree condition is sharp in general.     

(3,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7. Revised: September 21, 1998     

A Degree Constraint for Uniquely Hamiltonian Graphs

A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log₂n+2 where c=(log₂3−1)⁻¹≈1.71 thereby improving a bound given by Bondy and Jackson [3].     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

Cycle Lengths in Hamiltonian Graphs with a Pair of Vertices Having Large Degree Sum

A graph of order n is said to be pancyclic if it contains cycles of all lengths from three to n. Let G be a Hamiltonian graph and let x and y be vertices of G that are consecutive on some Hamiltonian cycle in G. Hakimi and Schmeichel showed (J Combin Theory Ser B 45:99–107, 1988) that if d(x) + d(y) ≥ n then either G is pancyclic, G has cycles of all lengths except n − 1 or G is isomorphic to a complete bipartite graph. In this paper, we study the existence of cycles of various lengths in a Hamiltonian graph G given the existence of a pair of vertices that have a high degree sum but are not adjacent on any Hamiltonian cycle in G.     

Spanning Trees with Few Leaves

In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k ≥ 2 and m ≥ 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n − k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win.