The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪··...The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪···∪V(Mk)covers V(G).This paper shows that,if G is a 3-regular claw-free graph,then imc(G)∈{2,3}.展开更多
Diab proved the following graphs are Cordial;Pm K1,n if and only if(m,n) =(1,2);Cm K1,n;Pm Kn;Cm Kn for all m and n except m ≡ 2(mod 4).In this paper,we proved the Cordiality on the union of 3-regular connected graph...Diab proved the following graphs are Cordial;Pm K1,n if and only if(m,n) =(1,2);Cm K1,n;Pm Kn;Cm Kn for all m and n except m ≡ 2(mod 4).In this paper,we proved the Cordiality on the union of 3-regular connected graph K3 and cycle Cm.First we have the Lemma 2,if uv ∈ E(G),G is Cordial,we add 4 vertices x,y,z,w in sequence to the edge uv,obtain a new graph denoted by G*,then G* is still Cordial,by this lemma,we consider four cases on the union of 3-regular connected graph R3,and for every case we distinguish four subcases on the cycle Cm.展开更多
A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vert...A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.展开更多
It is well-known that the Petersen graph is nonhamiltonian.A very short proof for this result was presented in[2]due to D.B.West.In this note,by extending the proof technique in[2],we briefly show that the girth of ev...It is well-known that the Petersen graph is nonhamiltonian.A very short proof for this result was presented in[2]due to D.B.West.In this note,by extending the proof technique in[2],we briefly show that the girth of every 3-regular hamiltonian graph on n≥10 vertices is at most(n+4)/3.展开更多
A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted by τC（G）,is the minimum cardinality of a clique-transversal set in G.In thi...A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted by τC（G）,is the minimum cardinality of a clique-transversal set in G.In this paper,we first present a lower bound on τC（G） and characterize the extremal graphs achieving the lower bound for a connected（claw,K4）-free 4-regular graph G.Furthermore,we show that for any 2-connected（claw,K4）-free 4-regular graph G of order n,its clique-transversal number equals to [n/3].展开更多
基金Supported by the National Natural Science Foundation of China（10771179）
文摘The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪···∪V(Mk)covers V(G).This paper shows that,if G is a 3-regular claw-free graph,then imc(G)∈{2,3}.
文摘Diab proved the following graphs are Cordial;Pm K1,n if and only if(m,n) =(1,2);Cm K1,n;Pm Kn;Cm Kn for all m and n except m ≡ 2(mod 4).In this paper,we proved the Cordiality on the union of 3-regular connected graph K3 and cycle Cm.First we have the Lemma 2,if uv ∈ E(G),G is Cordial,we add 4 vertices x,y,z,w in sequence to the edge uv,obtain a new graph denoted by G*,then G* is still Cordial,by this lemma,we consider four cases on the union of 3-regular connected graph R3,and for every case we distinguish four subcases on the cycle Cm.
文摘A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.
基金Supported by National Natural Science Foundation of China(Grant No.12071442)the Fundamental Research Funds for the Central Universities under(Grant No.020314380035)。
文摘It is well-known that the Petersen graph is nonhamiltonian.A very short proof for this result was presented in[2]due to D.B.West.In this note,by extending the proof technique in[2],we briefly show that the girth of every 3-regular hamiltonian graph on n≥10 vertices is at most(n+4)/3.
基金Supported by National Nature Science Foundation of China(Grant Nos.11171207 and 10971131)
文摘A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted by τC（G）,is the minimum cardinality of a clique-transversal set in G.In this paper,we first present a lower bound on τC（G） and characterize the extremal graphs achieving the lower bound for a connected（claw,K4）-free 4-regular graph G.Furthermore,we show that for any 2-connected（claw,K4）-free 4-regular graph G of order n,its clique-transversal number equals to [n/3].
