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.
Characterizing regular covers of symmetric graphs is one of the fundamental topics in the field of algebraic graph theory, and is often a key step for approaching general symmetric graphs. Complete graphs, which are t...Characterizing regular covers of symmetric graphs is one of the fundamental topics in the field of algebraic graph theory, and is often a key step for approaching general symmetric graphs. Complete graphs, which are typical symmetric graphs, naturally appear in the study of many symmetric graphs as normal quotient graphs. In this paper, a characterization of edge-transitive cyclic covers of complete graphs with prime power order is given by using the techniques of finite group theory and the related properties of coset graphs. Certain previous results are generalized and some new families of examples are founded.展开更多
For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of ...For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.展开更多
Let G be a simple graph with vertex set V(G) and edge set E(G). An edge coloring C of G is called an edge cover coloring, if each color appears at least once at each vertex . The maximum positive integer k such that G...Let G be a simple graph with vertex set V(G) and edge set E(G). An edge coloring C of G is called an edge cover coloring, if each color appears at least once at each vertex . The maximum positive integer k such that G has a k edge cover coloring is called the edge cover chromatic number of G and is denoted by . It is known that for any graph G, . If , then G is called a graph of CI class, otherwise G is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification on double graph of some graphs and a polynomial time algorithm can be obtained for actually finding such a classification by our proof.展开更多
An orthogonal double cover (ODC) of a graph H is a collection of subgraphs (pages) of H, so that they cover every edge of H twice and the intersection of any two of them contains exactly one edge. An ODC G of H is cyc...An orthogonal double cover (ODC) of a graph H is a collection of subgraphs (pages) of H, so that they cover every edge of H twice and the intersection of any two of them contains exactly one edge. An ODC G of H is cyclic (CODC) if the cyclic group of order is a subgroup of the automorphism group of G. In this paper, we introduce a general orthogonal labelling for CODC of circulant graphs and construct CODC by certain classes of graphs such as complete bipartite graph, the union of the co-cycles graph with a star, the center vertex of which, belongs to the co-cycles graph and graphs that are connected by a one vertex.展开更多
For the subset S■V(G), if every path with k vertices in a graph G contains at least one vertex from S, we call that S is a k-path vertex cover set of the graph G. Obviously, the subset is not unique. The cardinality ...For the subset S■V(G), if every path with k vertices in a graph G contains at least one vertex from S, we call that S is a k-path vertex cover set of the graph G. Obviously, the subset is not unique. The cardinality of the minimum k-path vertex cover set of a graph G is called the k-path vertex cover number, we denote it by ψk(G). In this paper, a lower or upper bound of ψk for some Cartesian product graphs is presented.展开更多
The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with...The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.展开更多
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展开更多
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.展开更多
Let G ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every ...Let G ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every E V（G）. An fractional f-indicator function is an function h that assigns to each edge of a graph G a number h（e） in [0, 1] so that for each vertex x, we have d^hG（x） = f（x）, where dh（x） = ∑ h（e） is the fractional degree xEe ofx inG. Set Eh = {e ： e e E（G） and h（e） ≠ 0}. IfGh isaspanningsubgraphofGsuchthat E（Gh） = Eh, then Gh is called an fractional f-factor of G. In this paper, we prove that for any binomial random graph Gn,p 2 with p 〉 n^-2/3, almost surely Gn,p contains an fractional f-factor.展开更多
A decomposition of a graph H is a partition of the edge set of H into edge-disjoint subgraphs . If for all , then G is a decomposition of H by G. Two decompositions and of the complete bipartite graph are orthogonal i...A decomposition of a graph H is a partition of the edge set of H into edge-disjoint subgraphs . If for all , then G is a decomposition of H by G. Two decompositions and of the complete bipartite graph are orthogonal if, for all . A set of decompositions of is a set of k mutually orthogonal graph squares (MOGS) if and are orthogonal for all and . For any bipartite graph G with n edges, denotes the maximum number k in a largest possible set of MOGS of by G. Our objective in this paper is to compute where is a path of length d with d + 1 vertices (i.e. Every edge of this path is one-to-one corresponding to an isomorphic to a certain graph F).展开更多
Ler G = （ V, E） be a finite simple graph and Pn denote the path of order n. A spanning subgraph F is called a { P2, P3 }-factor of G if each component of F is isomorphic to P2 or P3. With the path-covering method, i...Ler G = （ V, E） be a finite simple graph and Pn denote the path of order n. A spanning subgraph F is called a { P2, P3 }-factor of G if each component of F is isomorphic to P2 or P3. With the path-covering method, it is proved that any connected cubic graph with at least 5 vertices has a { P2, P3 }-factor F such that｜P3（F）｜P2（F）｜, where P2（F） and P3（F） denote the set of components of P2 and P3 in F, respectively.展开更多
Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x).In this paper,some sufficient conditions related to the connectivity and edge-connec...Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x).In this paper,some sufficient conditions related to the connectivity and edge-connectivity for a bipartite (mg,mf)-graph to have a (g,f)-factor with special properties are obtained and some previous results are generalized.Furthermore,the new results are proved to be the best possible.展开更多
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 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.展开更多
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.展开更多
The problem of deciding whether a graph manifold is finitely covered by a surface bundle over the circle is discussed in this paper.A necessary and sufficient condition in term of the solutions of a certain matrix equ...The problem of deciding whether a graph manifold is finitely covered by a surface bundle over the circle is discussed in this paper.A necessary and sufficient condition in term of the solutions of a certain matrix equation is obtained,as well as a necessary condition which is easy to compute. Our results sharpen and extend the earlier results of J.Leucke-Y.Wu,W.Neumann,and S.Wang-F. Yu in this topic.展开更多
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.展开更多
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 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.
文摘Characterizing regular covers of symmetric graphs is one of the fundamental topics in the field of algebraic graph theory, and is often a key step for approaching general symmetric graphs. Complete graphs, which are typical symmetric graphs, naturally appear in the study of many symmetric graphs as normal quotient graphs. In this paper, a characterization of edge-transitive cyclic covers of complete graphs with prime power order is given by using the techniques of finite group theory and the related properties of coset graphs. Certain previous results are generalized and some new families of examples are founded.
基金Supported by the Joint Fund of Liaoning Provincial Natural Science Foundation(Grant No.SY2016012)
文摘For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.
文摘Let G be a simple graph with vertex set V(G) and edge set E(G). An edge coloring C of G is called an edge cover coloring, if each color appears at least once at each vertex . The maximum positive integer k such that G has a k edge cover coloring is called the edge cover chromatic number of G and is denoted by . It is known that for any graph G, . If , then G is called a graph of CI class, otherwise G is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification on double graph of some graphs and a polynomial time algorithm can be obtained for actually finding such a classification by our proof.
文摘An orthogonal double cover (ODC) of a graph H is a collection of subgraphs (pages) of H, so that they cover every edge of H twice and the intersection of any two of them contains exactly one edge. An ODC G of H is cyclic (CODC) if the cyclic group of order is a subgroup of the automorphism group of G. In this paper, we introduce a general orthogonal labelling for CODC of circulant graphs and construct CODC by certain classes of graphs such as complete bipartite graph, the union of the co-cycles graph with a star, the center vertex of which, belongs to the co-cycles graph and graphs that are connected by a one vertex.
基金Supported by the National Natural Science Foundation of China(Grant Nos.61463026,61463027).
文摘For the subset S■V(G), if every path with k vertices in a graph G contains at least one vertex from S, we call that S is a k-path vertex cover set of the graph G. Obviously, the subset is not unique. The cardinality of the minimum k-path vertex cover set of a graph G is called the k-path vertex cover number, we denote it by ψk(G). In this paper, a lower or upper bound of ψk for some Cartesian product graphs is presented.
文摘The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.
基金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
基金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.
基金Supported by NSFSD(No.ZR2013AM001)NSFC(No.11001055),NSFC11371355
文摘Let G ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every E V（G）. An fractional f-indicator function is an function h that assigns to each edge of a graph G a number h（e） in [0, 1] so that for each vertex x, we have d^hG（x） = f（x）, where dh（x） = ∑ h（e） is the fractional degree xEe ofx inG. Set Eh = {e ： e e E（G） and h（e） ≠ 0}. IfGh isaspanningsubgraphofGsuchthat E（Gh） = Eh, then Gh is called an fractional f-factor of G. In this paper, we prove that for any binomial random graph Gn,p 2 with p 〉 n^-2/3, almost surely Gn,p contains an fractional f-factor.
文摘A decomposition of a graph H is a partition of the edge set of H into edge-disjoint subgraphs . If for all , then G is a decomposition of H by G. Two decompositions and of the complete bipartite graph are orthogonal if, for all . A set of decompositions of is a set of k mutually orthogonal graph squares (MOGS) if and are orthogonal for all and . For any bipartite graph G with n edges, denotes the maximum number k in a largest possible set of MOGS of by G. Our objective in this paper is to compute where is a path of length d with d + 1 vertices (i.e. Every edge of this path is one-to-one corresponding to an isomorphic to a certain graph F).
文摘Ler G = （ V, E） be a finite simple graph and Pn denote the path of order n. A spanning subgraph F is called a { P2, P3 }-factor of G if each component of F is isomorphic to P2 or P3. With the path-covering method, it is proved that any connected cubic graph with at least 5 vertices has a { P2, P3 }-factor F such that｜P3（F）｜P2（F）｜, where P2（F） and P3（F） denote the set of components of P2 and P3 in F, respectively.
基金Supported by the National Natural Science Foundation of China( 60 1 72 0 0 3) NSF of Shandongprovince ( Z2 0 0 0 A0 2 )
文摘Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x).In this paper,some sufficient conditions related to the connectivity and edge-connectivity for a bipartite (mg,mf)-graph to have a (g,f)-factor with special properties are obtained and some previous results are generalized.Furthermore,the new results are proved to be the best possible.
基金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.
基金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.
基金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.
文摘The problem of deciding whether a graph manifold is finitely covered by a surface bundle over the circle is discussed in this paper.A necessary and sufficient condition in term of the solutions of a certain matrix equation is obtained,as well as a necessary condition which is easy to compute. Our results sharpen and extend the earlier results of J.Leucke-Y.Wu,W.Neumann,and S.Wang-F. Yu in this topic.
文摘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.
基金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.
