A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken ove...A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.展开更多
M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + ...M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.展开更多
It is difficult to characterize graphs which contain no a 2-connected graph as a minor in graph theory.Let V_(8)be a graph constructed from an 8-cycle by connecting the antipodal vertices.There are thirteen 2-connecte...It is difficult to characterize graphs which contain no a 2-connected graph as a minor in graph theory.Let V_(8)be a graph constructed from an 8-cycle by connecting the antipodal vertices.There are thirteen 2-connected spanning subgraphs of V_(8).In particular,one of them is obtained from the Petersen graph by deleting two vertices and it is also a hard problem to characterize Petersen-minor-free graphs.In this paper,we characterize internally 4-connected graphs which contain a 2-connected spanning subgraph of V_(8)as a forbidden minor.展开更多
A connected graph G is said to be a factor-critical graph if G - v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly ｜E（G）｜＋ 1 maximum matchi...A connected graph G is said to be a factor-critical graph if G - v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly ｜E（G）｜＋ 1 maximum matchings is characterized.展开更多
For a prime p at least 5,let T=PSL(2,p).This paper gives a classification of the connected arc-transitive cubic Cayley graphs on T and a determination of the gener- ated pairs ((?),(?)) of T such that o((?))=2 and o((...For a prime p at least 5,let T=PSL(2,p).This paper gives a classification of the connected arc-transitive cubic Cayley graphs on T and a determination of the gener- ated pairs ((?),(?)) of T such that o((?))=2 and o((?))=3.展开更多
We discuss k-factors and Hamiltonian Graphs in graph theory. We prove a general version of the conjecture by R. Haggkvist; as a result, we prove two extended versions of two well-known theorems due to O. Ore and B. Ja...We discuss k-factors and Hamiltonian Graphs in graph theory. We prove a general version of the conjecture by R. Haggkvist; as a result, we prove two extended versions of two well-known theorems due to O. Ore and B. Jachson, respectively.展开更多
Many results have been obtained in investigating the existence of Hamiltonian cycles in 2-connected, k-regular graphs, see [3], [1], [4], [6] and [2].We consider only simple graphs here and use standard graph theory n...Many results have been obtained in investigating the existence of Hamiltonian cycles in 2-connected, k-regular graphs, see [3], [1], [4], [6] and [2].We consider only simple graphs here and use standard graph theory notations and terminology. We let V(G) and E(G) denote the vertex set and the edge set of graph G respectively.展开更多
Abstract An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v ∈ V（G） at most f（v） times. The f-core of G is the subgraph of G induced by the vertices v of degree d（v...Abstract An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v ∈ V（G） at most f（v） times. The f-core of G is the subgraph of G induced by the vertices v of degree d（v） = f（v）maxv∈y（G）{ [d（v）/f（v）l}. In this paper, we find some necessary conditions for a simple graph, whose f-core has maximum degree two, to be of class 2 for f-colorings.展开更多
In[1],P.Paulraja posed the following problem:Let G be a 2-connected graph suchthat δ(G)≥3,where δ(G)denotes the minimum degree of G.If each edge of G lies on either a cycle oflength 3 or a cycle of length 4,is it t...In[1],P.Paulraja posed the following problem:Let G be a 2-connected graph suchthat δ(G)≥3,where δ(G)denotes the minimum degree of G.If each edge of G lies on either a cycle oflength 3 or a cycle of length 4,is it true that G has a spanning Eulerian subgraph?A related case inwhich δ(G)≥4 is settled affairmatively in this paper.展开更多
文摘A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.
文摘M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.
基金Research Project supported by the National Natural Science Foundation of China(No.11961051)Provincial Natural Science Foundation of Shanxi(20210302123097)Shanxi Scholarship Council of China。
文摘It is difficult to characterize graphs which contain no a 2-connected graph as a minor in graph theory.Let V_(8)be a graph constructed from an 8-cycle by connecting the antipodal vertices.There are thirteen 2-connected spanning subgraphs of V_(8).In particular,one of them is obtained from the Petersen graph by deleting two vertices and it is also a hard problem to characterize Petersen-minor-free graphs.In this paper,we characterize internally 4-connected graphs which contain a 2-connected spanning subgraph of V_(8)as a forbidden minor.
基金supported by the National Natural Science Foundation of China(No.11551003)the Scientific research fund of the Science and Technology Program of Guangzhou,China(No.201510010265)the Qinghai Province Natural Science Foundation(No.2015-ZJ-911)
文摘A connected graph G is said to be a factor-critical graph if G - v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly ｜E（G）｜＋ 1 maximum matchings is characterized.
基金supported by the National natural Science Foundation of China(Grant No.10371003)Beijing Natural Science Foundation(Grant no.1052005)BMCE(Grant No.KM 2004 10028001).
文摘For a prime p at least 5,let T=PSL(2,p).This paper gives a classification of the connected arc-transitive cubic Cayley graphs on T and a determination of the gener- ated pairs ((?),(?)) of T such that o((?))=2 and o((?))=3.
基金supported by the Key Laboratory of Power System,Tsinghua University
文摘We discuss k-factors and Hamiltonian Graphs in graph theory. We prove a general version of the conjecture by R. Haggkvist; as a result, we prove two extended versions of two well-known theorems due to O. Ore and B. Jachson, respectively.
文摘Many results have been obtained in investigating the existence of Hamiltonian cycles in 2-connected, k-regular graphs, see [3], [1], [4], [6] and [2].We consider only simple graphs here and use standard graph theory notations and terminology. We let V(G) and E(G) denote the vertex set and the edge set of graph G respectively.
基金Supported by National Natural Science Foundation of China(Grant Nos.10901097,11001055)Tianyuan Youth Foundation of Mathematics(Grant No.10926099)+1 种基金Natural Science Foundation of Shandong(Grant No.ZR2010AQ003)Shandong Province Higher Educational Science and Technology Program(Grant No.G13LI04)of China
文摘Abstract An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v ∈ V（G） at most f（v） times. The f-core of G is the subgraph of G induced by the vertices v of degree d（v） = f（v）maxv∈y（G）{ [d（v）/f（v）l}. In this paper, we find some necessary conditions for a simple graph, whose f-core has maximum degree two, to be of class 2 for f-colorings.
基金The present work is supported by the National Natural Science Foundation of China
文摘In[1],P.Paulraja posed the following problem:Let G be a 2-connected graph suchthat δ(G)≥3,where δ(G)denotes the minimum degree of G.If each edge of G lies on either a cycle oflength 3 or a cycle of length 4,is it true that G has a spanning Eulerian subgraph?A related case inwhich δ(G)≥4 is settled affairmatively in this paper.
