Insertible vertices,neighborhood intersections,and hamiltonicity

Let G be a simple undirected graph of order n. For an independent set S ? V(G) of k vertices, we define the k neighborhood intersections S_i = {v ? V(G)\S|N(v) ∩ S| = i}, 1 ≦ i ≦ k, with s_i = |S_i|. Using the concept of insertible vertices and the concept of neighborhood intersections, we prove the following theorem.     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.     

Gargano,Lewinter and Malerba问题的解

§1　IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献   

A note on on-line ranking number of graphs

A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices of the same colour c contains an internal vertex with colour greater than c. The ranking number of a graph G is the smallest positive integer k admitting a k-ranking of G. In the on-line version of the problem, the vertices v ₁, v ², ..., v _n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G[{v ₁, v ₂, ..., v _i }] are known when the colour for the vertex v _i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k-ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n-partite graphs. The question of additivity and heredity is discussed as well.     

PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS

§1　IntroductionGraphs considered in this paper are finite and simple.For a graph G,its vertex setandedge set are denoted by V(G) and E(G) ,respectively.If vertices u and v are connected inG,the distance between u and v,denoted by d G(u,v) ,is the length ofa shortest(u,v) -pathin G.The diameter of a connected graph G is the maximum distance between two verticesof G.For X V(G) ,the neighbor set NG(X) of X is defined byNG(X) ={ y∈V(G) \X:there is x∈X such thatxy∈E(G) } .NG({ x} )…     

Two‐factors each component of which contains a specified vertex

It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v₁,v₂,…,v_k} ? V(G), there is a 2‐factor of G with precisely k cycles {C₁,C₂,…,C_k} such that v_i ∈ V(C_i) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003     

Degree sequences of graphs containing a cycle with prescribed length

Let r ≥ 3, n ≥ r and π = (d ₁, d ₂, ..., d _n ) be a non-increasing sequence of nonnegative integers. If π has a realization G with vertex set V (G) = {v ₁, v ₂, ..., v _n } such that d _G (v _i ) = d _i for i = 1, 2, ..., n and v ₁ v ₂ ... v _r v ₁ is a cycle of length r in G, then π is said to be potentially C _r ″-graphic. In this paper, we give a characterization for π to be potentially C _r ″-graphic. This work was supported by the grant of National Natural Science Foundation of China No. 10861006 and China Scholarship Council.     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.     

Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

Intersection theorems with geometric consequences

In this paper we prove that ifℱ is a family ofk-subsets of ann-set, μ₀, μ₁, ..., μ_s are distinct residues modp (p is a prime) such thatk ≡ μ₀ (modp) and forF ≠ F′ ≠ℱ we have |F ∩F′| ≡ μ_i (modp) for somei, 1 ≦i≦s, then |ℱ|≦( _s ⁿ ). As a consequence we show that ifR ⁿ is covered bym sets withm<(1+o(1)) (1.2) ⁿ then there is one set within which all the distances are realised. It is left open whether the same conclusion holds for compositep.     

Sphere and Dot Product Representations of Graphs

A graph G is a k-sphere graph if there are k-dimensional real vectors v ₁,…,v _n such that ij∈E(G) if and only if the distance between v _i and v _j is at most 1. A graph G is a k-dot product graph if there are k-dimensional real vectors v ₁,…,v _n such that ij∈E(G) if and only if the dot product of v _i and v _j is at least 1.     

Cohen-macaulay bipartite graphs

Let G be a graph on the vertex set V={x ₁, ..., x _n}. Let k be a field and let R be the polynomial ring k[x ₁, ..., x _n]. The graph ideal I(G), associated to G, is the ideal of R generated by the set of square-free monomials x _ix_j so that x _i, is adjacent to x _j. The graph G is Cohen-Macaulay over k if R/I(G) is a Cohen-Macaulay ring. Let G be a Cohen-Macaulay bipartite graph. The main result of this paper shows that G{v} is Cohen-Macaulay for some vertex v in G. Then as a consequence it is shown that the Reisner-Stanley simplicial complex of I(G) is shellable. An example of N. Terai is presented showing these results fail for Cohen-Macaulay non bipartite graphs. Partially supported by COFAA-IPN, CONACyT and SNI, México.     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

On H-Linked Graphs

For a fixed multigraph H, possibly containing loops, with V(H)={h₁, . . . , h_k}, we say a graph G is H-linked if for every choice of k vertices v₁, . . . , v_k in G, there exists a subdivision of H in G such that v_i represents h_i (for all i). This notion clearly generalizes the concept of k-linked graphs (as well as other properties). In this paper we determine, for a connected multigraph H and for any sufficiently large graph G, a sharp lower bound on δ(G) (depending upon H) such that G is H-linked.     

Covering a graph with cycles passing through given edges

We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e₁, …, e_k of G, there exist k vertex-disjoint cycles C₁, …, C_k in G such that e_i ∈ E(C_i) for all i ∈ {1, …, k} and V(C₁ ∪ ···∪ C_k) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997     

Hamiltonian Cycles in Almost Claw-Free Graphs

 Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove the following two results and conjecture that every 5-connected almost claw-free graph is hamiltonian. (1). Every 2-connected almost claw-free graph G∉J on n≤ 4 δ vertices is hamiltonian, where J is the set of all graphs defined as follows: any graph G in J can be decomposed into three disjoint connected subgraphs G ₁, G ₂ and G ₃ such that E _G (G _i , G _j ) = {u _i , u _j , v _i v _j } for i≠j and i,j = 1, 2, 3 (where u _i ≠v _i ∈V(G _i ) for i = 1, 2, 3). Moreover the bound 4δ is best possible, thereby fully generalizing several previous results. (2). Every 3-connected almost claw-free graph on at most 5δ−5 vertices is hamiltonian, hereby fully generalizing the corresponding result on claw-free graphs. Received: September 21, 1998 Final version received: August 18, 1999