A graph G is f-covered if each edge of G belongs to an f-factor. Some sufficient conditions for a graph to be f-covered are given.Katerinis'and Bermond's results are generalized.
The main contribution in this article is threefold:(1)we show the necessary and sufficient condition for graphs to be fractional(g,f)-covered which can be expressed in different forms,and extended to fractional(g,f,m)...The main contribution in this article is threefold:(1)we show the necessary and sufficient condition for graphs to be fractional(g,f)-covered which can be expressed in different forms,and extended to fractional(g,f,m)-covered graphs;(2)the concept of fractional-critical covered graph is put forward and its necessary and sufficient condition is given;(3)we present the degree condition for a graph to be fractional(g,f,n′,m)-critical covered,and show that degree bound is sharp when m is small.Moreover,the related result in fractional(a,b,n′,m)-critical covered setting is also verified.展开更多
A fractional[a,b]-factor of a graph G is a function h from E(G)to[0,1]satisfying a≤d^(h)_(G)(v)≤b for every vertex v of G,where d^(h)_(G)(v)=∑e∈E(v)h(e)and E(v)={e=uv:u∈V(G)}.A graph G is called fractional[a,b]-c...A fractional[a,b]-factor of a graph G is a function h from E(G)to[0,1]satisfying a≤d^(h)_(G)(v)≤b for every vertex v of G,where d^(h)_(G)(v)=∑e∈E(v)h(e)and E(v)={e=uv:u∈V(G)}.A graph G is called fractional[a,b]-covered if G contains a fractional[a,b]-factor h with h(e)=1 for any edge e of G.A graph G is called fractional(a,b,k)-critical covered if G—Q is fractional[a,b]-covered for any Q⊆V(G)with∣Q∣=k.In this article,we demonstrate a neighborhood condition for a graph to be fractional(a,b,k)-critical covered.Furthermore,we claim that the result is sharp.展开更多
Let B（G） denote the bipartite double cover of a non-bipartite graph G with v ≥ 2 vertices and s edges. We prove that G is a perfect 2-matching covered graph if and only if B（G） is a 1-extendable graph. Furthermor...Let B（G） denote the bipartite double cover of a non-bipartite graph G with v ≥ 2 vertices and s edges. We prove that G is a perfect 2-matching covered graph if and only if B（G） is a 1-extendable graph. Furthermore, we prove that B（G） is a minimally l-extendable graph if and only if G is a minimally perfect 2-matching covered graph and for each e = xy ∈ E（G）, there is an independent set S in G such that ｜ГG（S）｜ = ｜S｜ ＋ 1, x ∈ S and ｜ГG-xy（S）｜ = ｜S｜ Then, we construct a digraph D from B（G） or G and show that D is a strongly connected digraph if and only if G is a perfect 2-matching covered graph. So we design an algorithm in O（x√vε） time that determines whether G is a perfect 2-matching covered graph or not.展开更多
A graph G is called a fractional[a,b]-covered graph if for each e∈E(G),G contains a fractional[a,b]-factor covering e.A graph G is called a fractional(a,b,k)-critical covered graph if for any W■V(G)with|W|=k,G-W is ...A graph G is called a fractional[a,b]-covered graph if for each e∈E(G),G contains a fractional[a,b]-factor covering e.A graph G is called a fractional(a,b,k)-critical covered graph if for any W■V(G)with|W|=k,G-W is fractional[a,b]-covered,which was first defined and investigated by Zhou,Xu and Sun[S.Zhou,Y.Xu,Z.Sun,Degree conditions for fractional(a,b,k)-critical covered graphs,Information Processing Letters 152(2019)105838].In this work,we proceed to study fractional(a,b,k)-critical covered graphs and derive a result on fractional(a,b,k)-critical covered graphs depending on minimum degree and neighborhoods of independent sets.展开更多
Throughout this paper,D=（d<sub>1</sub>,d<sub>2</sub>,...,d<sub>n</sub>）denote a sequence of nonnegative inte-gers.We let（?）（D）denote the class of all graphs with degree sequen...Throughout this paper,D=（d<sub>1</sub>,d<sub>2</sub>,...,d<sub>n</sub>）denote a sequence of nonnegative inte-gers.We let（?）（D）denote the class of all graphs with degree sequence D,or equally,theclass of all symmetric（0,1）--matrices with trace 0 and row sum vector D.The structure matrix S=S（D） of D is a matrix of order n+1,whose entries展开更多
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 a...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)-factor if|NG(I)|>β(n-3k-1)+k for every independent set I of G with|I|=「β(2k+1)」;(ⅱ)a(k+1)-connected graph G of order n with n≥5k+2 is a P_(≥3)-factor covered graph if|NG(I)|>β(n-3k-1)+k+1 for every independent set I of G with|I|=「β(2k+1)」.展开更多
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...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.展开更多
In this paper, a characterization of all pentavalent arc-transitive graphs is given. It is shown that each pentavalent arc-transitive covering graph F is a regular simple or elementary abelian covering graph. In parti...In this paper, a characterization of all pentavalent arc-transitive graphs is given. It is shown that each pentavalent arc-transitive covering graph F is a regular simple or elementary abelian covering graph. In particular, the elementary abelian covering groups are Z3,Z5or a subgroup of Z2^5.展开更多
Enumerating the isomorphism classes of several types of graph covering projections is one of the central research topics in enumerative topological graph theory. A covering of G is called circulant if its covering gra...Enumerating the isomorphism classes of several types of graph covering projections is one of the central research topics in enumerative topological graph theory. A covering of G is called circulant if its covering graph is circulant. Recently, the authors [Discrete Math., 277, 73-85 （2004）1 enumerated the isomorphism classes of circulant double coverings of a certain type, called a typical covering, and showed that no double covering of a circulant graph of valency three is circulant. Also, in [Graphs and Combinatorics, 21,386 400 （2005）], the isomorphism classes of circulant double coverings of a circulant graph of valency four are enumerated. In this paper, the isomorphism classes of circulant double coverings of a circulant graph of valency five are enumerated.展开更多
A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p^3 for each prime p. Al...A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p^3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p^3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p^3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p^3 are all regular covers of the dipole Dip5 with covering transposition groups of order p^3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.展开更多
A regular graph X is called semisymmetric if it is edge-transitive but not vertex-transitive. For G ≤ AutX, we call a G-cover X semisymmetric if X is semisymmetric, and call a G-cover X one-regular if Aut X acts regu...A regular graph X is called semisymmetric if it is edge-transitive but not vertex-transitive. For G ≤ AutX, we call a G-cover X semisymmetric if X is semisymmetric, and call a G-cover X one-regular if Aut X acts regularly on its arc-set. In this paper, we give the sufficient and necessary conditions for the existence of one-regular or semisymmetric Zn-Covers of K3,3. Also, an infinite family of semisymmetric Zn×Zn-covers of K3,3 are constructed.展开更多
An independent set in a graph G is a set of pairwise non-adjacent vertices.Let ik(G)denote the number of independent sets of cardinality k in G.Then its generating function I(G;x)=∑^(α(G))^(k=0)ik(G)x^(k),is called ...An independent set in a graph G is a set of pairwise non-adjacent vertices.Let ik(G)denote the number of independent sets of cardinality k in G.Then its generating function I(G;x)=∑^(α(G))^(k=0)ik(G)x^(k),is called the independence polynomial of G(Gutman and Harary,1983).In this paper,we introduce a new graph operation called the cycle cover product and formulate its independence polynomial.We also give a criterion for formulating the independence polynomial of a graph.Based on the exact formulas,we prove some results on symmetry,unimodality,reality of zeros of independence polynomials of some graphs.As applications,we give some new constructions for graphs having symmetric and unimodal independence polynomials.展开更多
Enumerating the isomorphism or equivalence classes of several types of graph coverings is one of the central research topics in enumerative topological graph theory.A covering projection p from a Cayley graph Cay(Г,X...Enumerating the isomorphism or equivalence classes of several types of graph coverings is one of the central research topics in enumerative topological graph theory.A covering projection p from a Cayley graph Cay(Г,X)onto another Cayley graph Cay(Q,y)is called typical if the function p:Г→Q on the vertex sets is a group epimorphism.A typical covering is called abelian(or circulant,respectively)if its covering graph is a Cayley graph on an abelism(or a cyclic,respectively)group.Recently,the equivalence classes of connected abelian typical prime-fold coverings of a circulant graph are enumerated.As a continuation of this work,we enumerate the equivalence classes of connected abelian typical cube-free fold coverings of a circulant graph.展开更多
文摘A graph G is f-covered if each edge of G belongs to an f-factor. Some sufficient conditions for a graph to be f-covered are given.Katerinis'and Bermond's results are generalized.
基金the National Natural Science Foundation of China(Nos.12161 and 12031018).
文摘The main contribution in this article is threefold:(1)we show the necessary and sufficient condition for graphs to be fractional(g,f)-covered which can be expressed in different forms,and extended to fractional(g,f,m)-covered graphs;(2)the concept of fractional-critical covered graph is put forward and its necessary and sufficient condition is given;(3)we present the degree condition for a graph to be fractional(g,f,n′,m)-critical covered,and show that degree bound is sharp when m is small.Moreover,the related result in fractional(a,b,n′,m)-critical covered setting is also verified.
基金This work is supported by Six Big Talent Peak of Jiangsu Province,China(Grant No.JY-022).
文摘A fractional[a,b]-factor of a graph G is a function h from E(G)to[0,1]satisfying a≤d^(h)_(G)(v)≤b for every vertex v of G,where d^(h)_(G)(v)=∑e∈E(v)h(e)and E(v)={e=uv:u∈V(G)}.A graph G is called fractional[a,b]-covered if G contains a fractional[a,b]-factor h with h(e)=1 for any edge e of G.A graph G is called fractional(a,b,k)-critical covered if G—Q is fractional[a,b]-covered for any Q⊆V(G)with∣Q∣=k.In this article,we demonstrate a neighborhood condition for a graph to be fractional(a,b,k)-critical covered.Furthermore,we claim that the result is sharp.
基金Acknowledgements The authors would like to thank the referees very much for their careful reading and their very instructive suggestions which improve this paper greatly. This work was supported in part by the National Natural Science Foundation of China （Grant No. 11201158）.
文摘Let B（G） denote the bipartite double cover of a non-bipartite graph G with v ≥ 2 vertices and s edges. We prove that G is a perfect 2-matching covered graph if and only if B（G） is a 1-extendable graph. Furthermore, we prove that B（G） is a minimally l-extendable graph if and only if G is a minimally perfect 2-matching covered graph and for each e = xy ∈ E（G）, there is an independent set S in G such that ｜ГG（S）｜ = ｜S｜ ＋ 1, x ∈ S and ｜ГG-xy（S）｜ = ｜S｜ Then, we construct a digraph D from B（G） or G and show that D is a strongly connected digraph if and only if G is a perfect 2-matching covered graph. So we design an algorithm in O（x√vε） time that determines whether G is a perfect 2-matching covered graph or not.
文摘A graph G is called a fractional[a,b]-covered graph if for each e∈E(G),G contains a fractional[a,b]-factor covering e.A graph G is called a fractional(a,b,k)-critical covered graph if for any W■V(G)with|W|=k,G-W is fractional[a,b]-covered,which was first defined and investigated by Zhou,Xu and Sun[S.Zhou,Y.Xu,Z.Sun,Degree conditions for fractional(a,b,k)-critical covered graphs,Information Processing Letters 152(2019)105838].In this work,we proceed to study fractional(a,b,k)-critical covered graphs and derive a result on fractional(a,b,k)-critical covered graphs depending on minimum degree and neighborhoods of independent sets.
基金Supported by National Natural Science Foundation of China(No.19971086)
文摘Throughout this paper,D=（d<sub>1</sub>,d<sub>2</sub>,...,d<sub>n</sub>）denote a sequence of nonnegative inte-gers.We let（?）（D）denote the class of all graphs with degree sequence D,or equally,theclass of all symmetric（0,1）--matrices with trace 0 and row sum vector D.The structure matrix S=S（D） of D is a matrix of order n+1,whose entries
文摘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)-factor if|NG(I)|>β(n-3k-1)+k for every independent set I of G with|I|=「β(2k+1)」;(ⅱ)a(k+1)-connected graph G of order n with n≥5k+2 is a P_(≥3)-factor covered graph if|NG(I)|>β(n-3k-1)+k+1 for every independent set I of G with|I|=「β(2k+1)」.
基金Supported by Six Big Talent Peak of Jiangsu Province(Grant No.JY–022)333 Project of Jiangsu Provincethe National Natural Science Foundation of China(Grant No.11371009)。
文摘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.
基金Project supported by the National Natural Science Foundation of China (No.19831050, No.10171086) the Shanxi Provincial Natural Science Foundation of China (No.20011004)+1 种基金 the Key Program of the Ministry of Education of China (No.02023) the Returned A
文摘In this paper, a complete classification of arc-transitive cubic graphs of order 4p is given.
文摘In this paper, a characterization of all pentavalent arc-transitive graphs is given. It is shown that each pentavalent arc-transitive covering graph F is a regular simple or elementary abelian covering graph. In particular, the elementary abelian covering groups are Z3,Z5or a subgroup of Z2^5.
基金NSF of China(No.60473019 and 10571005)NKBRPC(2004CB318000)Com~2MaC-KOSEF in Korea
文摘Enumerating the isomorphism classes of several types of graph covering projections is one of the central research topics in enumerative topological graph theory. A covering of G is called circulant if its covering graph is circulant. Recently, the authors [Discrete Math., 277, 73-85 （2004）1 enumerated the isomorphism classes of circulant double coverings of a certain type, called a typical covering, and showed that no double covering of a circulant graph of valency three is circulant. Also, in [Graphs and Combinatorics, 21,386 400 （2005）], the isomorphism classes of circulant double coverings of a circulant graph of valency four are enumerated. In this paper, the isomorphism classes of circulant double coverings of a circulant graph of valency five are enumerated.
基金supported by National Natural Science Foundation of China (Grant Nos. 11571035 and 11231008)
文摘A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p^3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p^3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p^3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p^3 are all regular covers of the dipole Dip5 with covering transposition groups of order p^3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.
基金NSF of China (Project No.10571013)NSF of He'nan Province of China
文摘A regular graph X is called semisymmetric if it is edge-transitive but not vertex-transitive. For G ≤ AutX, we call a G-cover X semisymmetric if X is semisymmetric, and call a G-cover X one-regular if Aut X acts regularly on its arc-set. In this paper, we give the sufficient and necessary conditions for the existence of one-regular or semisymmetric Zn-Covers of K3,3. Also, an infinite family of semisymmetric Zn×Zn-covers of K3,3 are constructed.
基金Supported by National Natural Science Foundation of China(Grant Nos.11971206,12022105)Natural Science Foundation for Distinguished Young Scholars of Jiangsu Province(Grant No.BK20200048)。
文摘An independent set in a graph G is a set of pairwise non-adjacent vertices.Let ik(G)denote the number of independent sets of cardinality k in G.Then its generating function I(G;x)=∑^(α(G))^(k=0)ik(G)x^(k),is called the independence polynomial of G(Gutman and Harary,1983).In this paper,we introduce a new graph operation called the cycle cover product and formulate its independence polynomial.We also give a criterion for formulating the independence polynomial of a graph.Based on the exact formulas,we prove some results on symmetry,unimodality,reality of zeros of independence polynomials of some graphs.As applications,we give some new constructions for graphs having symmetric and unimodal independence polynomials.
基金The work was partially supported by the Korean-Russian bilateral project.The first author was supported by the Basic Science Research Program through the National Research Foundation of Korea(NRF)funded by the Ministry of Education(grant 2018R1D1A1B05048450),Korea.
文摘Enumerating the isomorphism or equivalence classes of several types of graph coverings is one of the central research topics in enumerative topological graph theory.A covering projection p from a Cayley graph Cay(Г,X)onto another Cayley graph Cay(Q,y)is called typical if the function p:Г→Q on the vertex sets is a group epimorphism.A typical covering is called abelian(or circulant,respectively)if its covering graph is a Cayley graph on an abelism(or a cyclic,respectively)group.Recently,the equivalence classes of connected abelian typical prime-fold coverings of a circulant graph are enumerated.As a continuation of this work,we enumerate the equivalence classes of connected abelian typical cube-free fold coverings of a circulant graph.
