二部定向图的最长通路和圈

Let D be a bipartite oriented graph in which the indegree and outdegree of each vertex are at least k. The result given in this paper is that D contains either a cycle of length at least 4k or a path of length at least 4k + 1. Jackson [1] declared that: if |V(D) |≤4k,D contains a Hamiltonian cycle. Evidently, the result Of this paper implies the result given by Jackson.     

Degree Conditions for k-Hamiltonian [a,b]-factors

Let a,b,k be nonnegative integers with 2≤a相似文献   

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.     

Path Factors and Neighborhoods of Independent Sets in Graphs

A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices.Let k≥2 be an integer.A P_≥k-factor of G means a path factor in which each component is a path with at least k vertices.A graph G is a P_≥k-factor covered graph if for any e∈E(G),G has a P_≥k-factor including e.Let β be a real number with 1/3≤β≤1 and k be a positive integer.We verify that(ⅰ) a k-connected graph G of order n with n≥5k+2 has a P_≥3...     

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.     

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     

1-planar Graphs without 4-cycles or 5-cycles are 5-colorable

A graph is 1-planar if it can be drawn on the Euclidean plane so that each edge is crossed by at most one other edge. A proper vertex k-coloring of a graph G is defined as a vertex coloring from a set of k colors such that no two adjacent vertices have the same color. A graph that can be assigned a proper k-coloring is k-colorable. A cycle is a path of edges and vertices wherein a vertex is reachable from itself. A cycle contains k vertices and k edges is a k-cycle. In this paper, it is proved t...     

On Some Cycles in Wenger Graphs

Let p be a prime,q be a power of p,and let Fq be the field of q elements.For any positive integer n,the Wenger graph Wn(q)is defined as follows:it is a bipartite graph with the vertex partitions being two copies of the(n+1)-dimensional vector space Fq^n+1,and two vertices p=(p(1),…,p(n+1))and l=[l(1),…,l(n+1)]being adjacent if p(i)+l(i)=p(1)l(1)i-1,for all i=2,3,…,n+1.In 2008,Shao,He and Shan showed that for n≥2,Wn(q)contains a cycle of length 2 k where 4≤k≤2 p and k≠5.In this paper we extend their results by showing that(i)for n≥2 and p≥3,Wn(q)contains cycles of length 2k,where 4≤k≤4 p+1 and k≠5;(ii)for q≥5,0相似文献   

Some Existence Theorems on Path Factors with Given Properties in Graphs

A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥_n-factor if its each component admits at least n vertices. A graph G is called P≥_n-factor covered if G admits a P≥_n-factor containing e for any e ∈ E(G), which is defined by[Discrete Mathematics, 309, 2067–2076(2009)]. We first define the concept of a(P≥_n, k)-factor-critical covered graph, namely, a graph G is called(P≥_n, k)-factor-critical covered if G-D is P≥_n-factor covered for any D ? V(G) with |D| = k. In this paper, we verify that(i) a graph G with κ(G) ≥ k + 1 is(P≥2, k)-factor-critical covered if bind(G) 2+k/3;(ii) a graph G with |V(G)| ≥ k + 3 and κ(G) ≥ k + 1 is(P≥3, k)-factor-critical covered if bind(G) ≥4+k/3.     

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.     

三边连通超欧拉图的一个注记

For two integers l 0 and k ≥ 0,define C(l,k) to be the family of 2-edge connected graphs such that a graph G ∈ C(l,k) if and only if for every bond S-E(G) with |S| ≤ 3,each component of G-S has order at least(|V(G)|-k)/l.In this note we prove that if a 3-edge-connected simple graph G is in C(10,3),then G is supereulerian if and only if G cannot be contracted to the Petersen graph.Our result extends an earlier result in [Supereulerian graphs and Petersen graph.JCMCC 1991,9:79-89] by Chen.     

Heavy cycles in 2-connected triangle-free weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex v is called the weighted degree of v, denoted by dw(v). The weight of a cycle is defined as the sum of the weights of its edges. Fujisawa proved that if G is a 2-connected triangle-free weighted graph such that the minimum weighted degree of G is at least d, then G contains a cycle of weight at least 2d. In this paper, we proved that if G is a2-connected triangle-free weighted graph of even size such that dw(u) + dw(v) ≥ 2d holds for any pair of nonadjacent vertices u, v ∈ V(G), then G contains a cycle of weight at least 2d.     

VERTEX-FAULT-TOLERANT CYCLES EMBEDDING ON ENHANCED HYPERCUBE NETWORKS

In this paper, we study the enhanced hypercube, an attractive variant of the hypercube and obtained by adding some complementary edges from a hypercube, and focus on cycles embedding on the enhanced hypercube with faulty vertices. Let Fu be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k （n ≥ 3, 1 ≤ k 〈≤n - 1）. When IFvl = 2, we showed that Qn,k - Fv contains a fault-free cycle of every even length from 4 to 2n - 4 where n （n ≥ 3） and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2n - 4, simultaneously, contains a cycle of every odd length from n-k ＋ 2 to 2^n-3 where n （≥ 3） and k have the different parity. Furthermore, when ｜Fv｜ = fv ≤ n - 2, we prove that there exists the longest fault-free cycle, which is of even length 2^n - 2fv whether n （n ≥ 3） and k have the same parity or not; and there exists the longest fault-free cycle, which is of odd length 2^n - 2fv ＋ 1 in Qn,k - Fv where n （≥ 3） and k have the different parity.     

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.     

DNA labelled graphs with DNA computing

Let k≥2, 1≤i≤k andα≥1 be three integers. For any multiset which consists of some k-long oligonucleotides, a DNA labelled graph is defined as follows: each oligonucleotide from the multiset becomes a point; two points are connected by an arc from the first point to the second one if the i rightmost uucleotides of the first point overlap with the i leftmost nucleotides of the second one. We say that a directed graph D can be(k, i;α)-labelled if it is possible to assign a label(l_1(x),..., l_k(x))to each point x of D such that l_j(x)∈{0,...,a-1}for any j∈{1,...,k}and(x,y)∈E(D)if and only if(l_k-i 1(x),..., l_k(x))=(l_1(y),..., l_i(y)). By the biological background, a directed graph is a DNA labelled graph if there exist two integers k, i such that it is(k, i; 4)-labelled. In this paper, a detailed discussion of DNA labelled graphs is given. Firstly, we study the relationship between DNA labelled graphs and some existing directed graph classes. Secondly, it is shown that for any DNA labelled graph, there exists a positive integer i such that it is(2i, i; 4)-labelled. Furthermore, the smallest i is determined, and a polynomial-time algorithm is introduced to give a(2i, i; 4)-labelling for a given DNA labelled graph. Finally, a DNA algorithm is given to find all paths from one given point to another in a(2i, i; 4)-labelled directed graph.     

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.     

The Second Neighbourhood for Quasi-transitive Oriented Graphs

In 2006, Sullivan stated the conjectures:(1) every oriented graph has a vertex x such that d~(++)(x) ≥ d~-(x);(2) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 d~-(x);(3) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 · min{d~+(x), d~-(x)}. A vertex x in D satisfying Conjecture(i) is called a Sullivan-i vertex, i = 1, 2, 3. A digraph D is called quasi-transitive if for every pair xy, yz of arcs between distinct vertices x, y, z, xz or zx("or" is inclusive here) is in D. In this paper, we prove that the conjectures hold for quasi-transitive oriented graphs, which is a superclass of tournaments and transitive acyclic digraphs. Furthermore, we show that a quasi-transitive oriented graph with no vertex of in-degree zero has at least three Sullivan-1 vertices and a quasi-transitive oriented graph has at least three Sullivan-3 vertices unless it belongs to an exceptional class of quasitransitive oriented graphs. For Sullivan-2 vertices, we show that an extended tournament, a subclass of quasi-transitive oriented graphs and a superclass of tournaments, has at least two Sullivan-2 vertices unless it belongs to an exceptional class of extended tournaments.     

The Criticality for Circular Coloring of Graph G_d~k

For two positive integers k and d such that k ≥ 2d, Gkd is the graph with vertex set {0,1, ...,k-1} in which ij is an edge if and only if d ≤ |i-j| ≤ k-d. Clearly, Gk1 is a complete graph of k vertices and we always assume d ≥ 2 in the following. It is easy to see (also [1]) that a graph G is (k, d)-colorable if and only if there exists a homomorphism from G to Gkd.     

关于H-cordial图和semi-H-cordial图的若干结论（英文）

I. Cahit calls a graph H-cordial if it is possible to label the edges with the numbers from the set{1,-1} in such a way that, for some k, at each vertex v the sum of the labels on the edges incident with v is either k or-k and the inequalities |v(k)-v(-k)| ≤ 1 and|e(1)-e(-1)| ≤ 1 are also satisfied. A graph G is called to be semi-H-cordial, if there exists a labeling f, such that for each vertex v, |f(v)| ≤ 1, and the inequalities |e_f(1)-e_f(-1)| ≤ 1 and |vf(1)-vf(-1)| ≤ 1 are also satisfied. An odd-degree(even-degree) graph is a graph that all of the vertex is odd(even) vertex. Three conclusions were proved:(1) An H-cordial graph G is either odd-degree graph or even-degree graph;(2) If G is an odd-degree graph, then G is H-cordial if and only if |E(G)| is even;(3) A graph G is semi-H-cordial if and only if |E(G)| is even and G has no Euler component with odd edges.     

GENERAL THEORETICAL RESULTS ON RECTILINEAR EMBEDABILITY OF GRAPHS

In the design of certain kinds of electronic circuits the following question arises:given a non-negative integer k, what graphs admit of a plane embedding such that every edge is a broken lineformed by horizontal and vertical segments and having at mort k bends? Any such graph is said tobe k--rectilinear. No matter what k is, an obvious necessary condition for k-rectilinearity is that thedegree of each vertex does not exceed four.Our main result is that every planar graph H satisfying this condition is 3--rectilinear:in fact,it is 2--rectilinear with the only exception of the octahedron. We also outline a polynomial-timealgorithm which actually constructs a plane embedding of H with at most 2 bends (3 bends if H isthe octahedron) on each edge. The resulting embedding has the property that the total number ofbends does not exceed 2n, where n is the number of vertices of H.