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.展开更多
The technique of contractions and the known results in the study of cycles in 3-connected cubic graphs are applied to obtain the following result. Let G be a 3-connected cubic graph, X C V（G） with ｜X｜ = 16 and e ...The technique of contractions and the known results in the study of cycles in 3-connected cubic graphs are applied to obtain the following result. Let G be a 3-connected cubic graph, X C V（G） with ｜X｜ = 16 and e ∈ E（G）. Then either for every 8-subset A of X, A U {e} is cyclable or for some 14-subset A of X, A U {e} is cyelable.展开更多
Let G=(V,E)be a graph.For a vertex labeling f:V→Z2,it induces an edge labeling f+:E→Z2,where for each edge v1 v2∈E we have f+(v1 v2)=f(v1)+f(v2).For each i∈Z2,we use vf(i)(respectively,ef(i))to denote the number o...Let G=(V,E)be a graph.For a vertex labeling f:V→Z2,it induces an edge labeling f+:E→Z2,where for each edge v1 v2∈E we have f+(v1 v2)=f(v1)+f(v2).For each i∈Z2,we use vf(i)(respectively,ef(i))to denote the number of vertices(respectively,edges)with label i.A vertex labeling f of G is said to be friendly if vertices with different labels differ in size by at most one.The full friendly index set of a graph G,denoted by F F I(G),consists of all possible values of ef(1)-ef(0),where f ranges over all friendly labelings of G.In this paper,motivated by a problem raised by[6],we study the full friendly index sets of a family of cubic graphs.展开更多
Let G be a graph and C be an arbitrary even cycle of G.The graph G is called a cycle-forced graph if G-V(C)has a unique perfect matching.When C is an arbitrary induced even cycle of G,G is called an induced-cycle-forc...Let G be a graph and C be an arbitrary even cycle of G.The graph G is called a cycle-forced graph if G-V(C)has a unique perfect matching.When C is an arbitrary induced even cycle of G,G is called an induced-cycle-forced graph.If G-V(C)has no perfect matching,G is said to be cycle-bad.This paper gives characterizations of these three type of graphs in the class of 2-connected claw-free cubic graphs.展开更多
The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are supe...The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are super-edge-graceful. A conjecture is proposed.展开更多
An upper bound is established on the parameter Γ -(G) for a cubic graph G and two infinite families of 3-connected graphs G k, G * k are constructed to show that the bound is sharp and, moreover, the difference Γ -(...An upper bound is established on the parameter Γ -(G) for a cubic graph G and two infinite families of 3-connected graphs G k, G * k are constructed to show that the bound is sharp and, moreover, the difference Γ -(G * k)-γ s(G * k) can be arbitrarily large, where Г -(G * k) and γ s(G * k) are the upper minus domination and signed domination numbers of G * k, respectively. Thus two open problems are solved.展开更多
Suppose that G is a planar cubic graph withχi(G)>5.We show that ifχi(H)<χi(G)for each planar cubic graph H of order less thanG,thenG is either a 3-connected simple planar cubic graph,or a planar graph obtaine...Suppose that G is a planar cubic graph withχi(G)>5.We show that ifχi(H)<χi(G)for each planar cubic graph H of order less thanG,thenG is either a 3-connected simple planar cubic graph,or a planar graph obtained from a simple cubic 3-connected planar graph by adding some earrings.This shows that a minimum non-5-injectively colorable simple planar cubic graph must be 3-connected.展开更多
Let be a connected Cayley graph of group G, then Γ is called normal if the right regular representation of G is a normal subgroup of , the full automorphism group of Γ. For the case where G is a finite nonabelian si...Let be a connected Cayley graph of group G, then Γ is called normal if the right regular representation of G is a normal subgroup of , the full automorphism group of Γ. For the case where G is a finite nonabelian simple group and Γ is symmetric cubic Cayley graph, Caiheng Li and Shangjin Xu proved that Γ is normal with only two exceptions. Since then, the normality of nonsymmetric cubic Cayley graph of nonabelian simple group aroused strong interest of people. So far such graphs which have been known are all normal. Then people conjecture that all of such graphs are either normal or the Cayley subset consists of involutions. In this paper we give an negative answer by two counterexamples. As far as we know these are the first examples for the non-normal cubic nonsymmetric Cayley graphs of finite nonabelian simple groups.展开更多
In this paper,we are dealing with the study of the metric dimension of some classes of regular graphs by considering a class of bridgeless cubic graphs called the flower snarks Jn,a class of cubic convex polytopes con...In this paper,we are dealing with the study of the metric dimension of some classes of regular graphs by considering a class of bridgeless cubic graphs called the flower snarks Jn,a class of cubic convex polytopes considering the open problem raised in[M.Imran et al.,families of plane graphs with constant metric dimension,Utilitas Math.,in press]and finally Harary graphs H5,n by partially answering to an open problem proposed inⅡ.Javaid et al.,Families of regular graphs with constant metric dimension,Utilitas Math.,2012,88:43-57].We prove that these classes of regular graphs have constant metric dimension.展开更多
A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa（ G）,is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a...A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa（ G）,is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a forest whose components are stars of order at most k ＋ 1. The k-star arboricity of a graph G,denoted by sak（ G）,is the minimum number of k-star forests needed to decompose G. In this paper,it is proved that if any two vertices of degree 3 are nonadjacent in a subcubic graph G then sa2（ G） ≤2.For general subcubic graphs G, a polynomial-time algorithm is described to decompose G into three 2-star forests. For a tree T and[Δ k, T）/k]t≤ sak（ T） ≤[Δ（ T）- 1/K]＋1,where Δ（ T） is the maximum degree of T.kMoreover,a linear-time algorithm is designed to determine whether sak（ T） ≤m for any tree T and any positive integers m and k.展开更多
In 1994, FAN and RASPAUD posed the following conjecture: every bridgeless cubic graph contains three perfect matchings M 1, M 2 and M 3 such that M 1∩M 2∩M 3=*I.In this paper we obtain the following result: l...In 1994, FAN and RASPAUD posed the following conjecture: every bridgeless cubic graph contains three perfect matchings M 1, M 2 and M 3 such that M 1∩M 2∩M 3=*I.In this paper we obtain the following result: let G be a cyclely-4-edge-connected cubic graph, which has a perfect matching M 1 such that G-M 1 consists of four odd cycles. Then G contains two perfect matchings M 2 and M 3 such that M 1∩M 2∩M 3=*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.
基金Supported by the National Natural Science Foundation of China(Grant No.10971027)
文摘The technique of contractions and the known results in the study of cycles in 3-connected cubic graphs are applied to obtain the following result. Let G be a 3-connected cubic graph, X C V（G） with ｜X｜ = 16 and e ∈ E（G）. Then either for every 8-subset A of X, A U {e} is cyclable or for some 14-subset A of X, A U {e} is cyelable.
基金Supported by the National Natural Science Foundation of China(Grant No.11801149)Doctoral Fund of Henan Polytechnic University(Grant No.B2018-55)。
文摘Let G=(V,E)be a graph.For a vertex labeling f:V→Z2,it induces an edge labeling f+:E→Z2,where for each edge v1 v2∈E we have f+(v1 v2)=f(v1)+f(v2).For each i∈Z2,we use vf(i)(respectively,ef(i))to denote the number of vertices(respectively,edges)with label i.A vertex labeling f of G is said to be friendly if vertices with different labels differ in size by at most one.The full friendly index set of a graph G,denoted by F F I(G),consists of all possible values of ef(1)-ef(0),where f ranges over all friendly labelings of G.In this paper,motivated by a problem raised by[6],we study the full friendly index sets of a family of cubic graphs.
基金Supported by National Natural Science Foundation of China(Grant Nos.12171440 and 11971445)。
文摘Let G be a graph and C be an arbitrary even cycle of G.The graph G is called a cycle-forced graph if G-V(C)has a unique perfect matching.When C is an arbitrary induced even cycle of G,G is called an induced-cycle-forced graph.If G-V(C)has no perfect matching,G is said to be cycle-bad.This paper gives characterizations of these three type of graphs in the class of 2-connected claw-free cubic graphs.
基金Partially supported by Faculty-Research Grant,Hong Kong Baptist University
文摘The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are super-edge-graceful. A conjecture is proposed.
文摘An upper bound is established on the parameter Γ -(G) for a cubic graph G and two infinite families of 3-connected graphs G k, G * k are constructed to show that the bound is sharp and, moreover, the difference Γ -(G * k)-γ s(G * k) can be arbitrarily large, where Г -(G * k) and γ s(G * k) are the upper minus domination and signed domination numbers of G * k, respectively. Thus two open problems are solved.
基金This research was supported by the National Natural Science Foundation of China(Nos.11571180 and 11331003)the Natural Science Foundation of Jiangsu Higher Education Institutions of China(No.17KJB110010).
文摘Suppose that G is a planar cubic graph withχi(G)>5.We show that ifχi(H)<χi(G)for each planar cubic graph H of order less thanG,thenG is either a 3-connected simple planar cubic graph,or a planar graph obtained from a simple cubic 3-connected planar graph by adding some earrings.This shows that a minimum non-5-injectively colorable simple planar cubic graph must be 3-connected.
基金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.
文摘Let be a connected Cayley graph of group G, then Γ is called normal if the right regular representation of G is a normal subgroup of , the full automorphism group of Γ. For the case where G is a finite nonabelian simple group and Γ is symmetric cubic Cayley graph, Caiheng Li and Shangjin Xu proved that Γ is normal with only two exceptions. Since then, the normality of nonsymmetric cubic Cayley graph of nonabelian simple group aroused strong interest of people. So far such graphs which have been known are all normal. Then people conjecture that all of such graphs are either normal or the Cayley subset consists of involutions. In this paper we give an negative answer by two counterexamples. As far as we know these are the first examples for the non-normal cubic nonsymmetric Cayley graphs of finite nonabelian simple groups.
基金supported by National University of Sceinces and Technology(NUST)Islamabad+1 种基金grant of Higher Education Commission of Pakistan Ref.No:PMIPFP/HRD/HEC/2011/3386support of Slovak VEGA Grant 1/0130/12
文摘In this paper,we are dealing with the study of the metric dimension of some classes of regular graphs by considering a class of bridgeless cubic graphs called the flower snarks Jn,a class of cubic convex polytopes considering the open problem raised in[M.Imran et al.,families of plane graphs with constant metric dimension,Utilitas Math.,in press]and finally Harary graphs H5,n by partially answering to an open problem proposed inⅡ.Javaid et al.,Families of regular graphs with constant metric dimension,Utilitas Math.,2012,88:43-57].We prove that these classes of regular graphs have constant metric dimension.
基金National Natural Science Foundation of China(No.10971025)
文摘A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa（ G）,is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a forest whose components are stars of order at most k ＋ 1. The k-star arboricity of a graph G,denoted by sak（ G）,is the minimum number of k-star forests needed to decompose G. In this paper,it is proved that if any two vertices of degree 3 are nonadjacent in a subcubic graph G then sa2（ G） ≤2.For general subcubic graphs G, a polynomial-time algorithm is described to decompose G into three 2-star forests. For a tree T and[Δ k, T）/k]t≤ sak（ T） ≤[Δ（ T）- 1/K]＋1,where Δ（ T） is the maximum degree of T.kMoreover,a linear-time algorithm is designed to determine whether sak（ T） ≤m for any tree T and any positive integers m and k.
文摘In 1994, FAN and RASPAUD posed the following conjecture: every bridgeless cubic graph contains three perfect matchings M 1, M 2 and M 3 such that M 1∩M 2∩M 3=*I.In this paper we obtain the following result: let G be a cyclely-4-edge-connected cubic graph, which has a perfect matching M 1 such that G-M 1 consists of four odd cycles. Then G contains two perfect matchings M 2 and M 3 such that M 1∩M 2∩M 3=*I.
