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.     

On κ—ordered Graphs Involved Degree Sum

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

Rainb ow Vertex-connection Numb er of Ladder and M¨obius Ladder

A vertex-colored graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. If for every pair u, v of distinct vertices, G contains a rainbow u-v geodesic, then G is strong rainbow vertex-connected. The minimum number k for which there exists a k-vertex-coloring of G that results in a strongly rainbow vertex-connected graph is called the strong rainbow vertex-connection number of G, denoted by srvc(G). Observe that rvc(G) ≤ srvc(G) for any nontrivial connected graph G. In this paper, for a Ladder Ln, we determine the exact value of srvc(Ln) for n even. For n odd, upper and lower bounds of srvc(Ln) are obtained. We also give upper and lower bounds of the (strong) rainbow vertex-connection number of M¨obius Ladder.     

Ladder图和Mbius Ladder图的彩虹点连通数（英文）

A vertex-colored graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. If for every pair u, v of distinct vertices, G contains a rainbow u-v geodesic, then G is strong rainbow vertex-connected. The minimum number k for which there exists a k-vertex-coloring of G that results in a strongly rainbow vertex-connected graph is called the strong rainbow vertex-connection number of G, denoted by srvc(G). Observe that rvc(G) ≤ srvc(G) for any nontrivial connected graph G. In this paper, for a Ladder L_n,we determine the exact value of srvc(L_n) for n even. For n odd, upper and lower bounds of srvc(L_n) are obtained. We also give upper and lower bounds of the(strong) rainbow vertex-connection number of Mbius Ladder.     

ON THE UPPER GENERALIZED EXPONENTS OF MINISTRONG DIGRAPHS

A digraph G is called primitive if there ekists a positive integer k such that there isa walk of length k from u to v for each ordered pair of not necessarily distinct vertices uand v. The smallest such k is called the exponent of G, denoted by γ(G). Exponents forprimitive digraphs have been studied extensively due to their intrinsic importance in graphtheory, combinatorics, matrix theory, and their applications in communication problems. Asa generalization of exponents, Brualdi and Liu[1] …     

3,4跳图的平面性

For a graph G of size ε≥1 and its edge-induced subgraphs H1 and H2 of size r(1≤r≤ε), H1 is said to be obtained from H2 by an edge jump if there exist four distinct vertices u,v,w and x in G such that (u,v)∈E(H2), (w,x)∈ E(G)-E(H2) and H1=H2-(u,v)+(w,x). In this article, the r-jump graphs (r≥3) are discussed. A graph H is said to be an r-jump graph of G if its vertices correspond to the edge induced graph of size r in G and two vertices are adjacent if and only if one of the two corresponding subgraphs can be obtained from the other by an edge jump. For k≥2, the k-th iterated r-jump graph Jrk(G) is defined as Jr(Jrk-1(G)), where Jr1(G)=Jr(G).An infinite sequence{Gi} of graphs is planar if every graph Gi is planar. It is shown that there does not exist a graph G for which the sequence {J3k(G)} is planar, where k is any positive integer. Meanwhile,lim gen(J3k(G))=∞,where gen(G) denotes the genus of a graph G, if the sequencek→∞J3k(G) is defined for every positive integer k. As for the 4-jump gra     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

Distributing pairs of vertices on Hamiltonian cycles

Let G be a graph of order n with minimum degree δ(G)≥n/2+1. Faudree and Li(2012) conjectured that for any pair of vertices x and y in G and any integer 2≤k≤n/2, there exists a Hamiltonian cycle C such that the distance between x and y on C is k. In this paper, we prove that this conjecture is true for graphs of sufficiently large order. The main tools of our proof are the regularity lemma of Szemer′edi and the blow-up lemma of Koml′os et al.(1997).     

The Rainbow Vertex-disconnection in Graphs

Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.     

Acyclic 6-choosability of Planar Graphs without 5-cycles and Adjacent 4-cycles

A proper vertex coloring of a graph is acyclic if every cycle uses at least three colors. A graph G is acyclically k-choosable if for any list assignment L = {L(v) : v ∈ V(G)} with |L(v)| ≥ k for all v ∈ V(G), there exists a proper acyclic vertex coloring φ of G such that φ(v) ∈ L(v) for all v ∈ V(G). In this paper, we prove that if G is a planar graph and contains no 5-cycles and no adjacent 4-cycles, then G is acyclically 6-choosable.     

3-连通3-正则图中的可序子集

图G的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题.     

Existence of openly disjoint circuits through a vertex

We deal with conditions for a digraph of minimum degree r which imply the existence of a vertex x contained in r circuits which have pairwise only x in common. In particular, we give some positive answers to a question of P. Seymour, whether an r‐regular digraph has a vertex x which is contained in r circuits pairwise disjoint except for x, and show that the answer, in general, is negative. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 93–105, 2010     

On the structure of strong 3-quasi-transitive digraphs

In this paper, D=(V(D),A(D)) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V(D). Given a digraph D, we say that D is 3-quasi-transitive if, whenever u→v→w→z in D, then u and z are adjacent or u=z. In Bang-Jensen (2004) [3], Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs.     

Degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number

Let $D$ be a finite and simple digraph with vertex set $V\left(D\right)$. For a vertex $v\in V\left(D\right)$, the degree $d\left(v\right)$ of $v$ is defined as the minimum value of its out-degree $d^{+}\left(v\right)$ and its in-degree $d^{?}\left(v\right)$. If $D$ is a graph or a digraph with minimum degree $\delta$ and edge-connectivity $\lambda$, then $\lambda \le \delta$. A graph or a digraph is maximally edge-connected if $\lambda =\delta$. A graph or a digraph is called super-edge-connected if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree.In this note we present degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number of the underlying graph.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.     

A note on total colourings of digraphs

In the paper two different arc-colourings and two associated with the total colourings of digraphs are considered. In one of these colourings we show that the problem of calculating the total chromatic index reduces to that of calculating the chromatic number of the underlying graph. In the other colouring we find the total chromatic indices of complete symmetric digraphs and tournaments.     

Finding cheapest cycles in vertex-weighted quasi-transitive and extended semicomplete digraphs

We consider the problem of finding a minimum cost cycle in a digraph with real-valued costs on the vertices. This problem generalizes the problem of finding a longest cycle and hence is NP-hard for general digraphs. We prove that the problem is solvable in polynomial time for extended semicomplete digraphs and for quasi-transitive digraphs, thereby generalizing a number of previous results on these classes. As a byproduct of our method we develop polynomial algorithms for the following problem: Given a quasi-transitive digraph D with real-valued vertex costs, find, for each j=1,2,…,|V(D)|, j disjoint paths P₁,P₂,…,P_j such that the total cost of these paths is minimum among all collections of j disjoint paths in D.     

Automorphisms of endomorphism semigroups of reflexive digraphs

A reflexive digraph is a pair (X, ρ), where X is an arbitrary set and ρ is a reflexive binary relation on X. Let End (X, ρ) be the semigroup of endomorphisms of (X, ρ). We determine the group of automorphisms of End (X, ρ) for: digraphs containing an edge not contained in a cycle, digraphs consisting of arbitrary unions of cycles such that cycles of length ≥2 are pairwise disjoint, and some circulant digraphs (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)