The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs”

The contractible subgraph of 5 -connected graphs

Chengfu Qin, Xiaofeng Guo, Weihua Yang (2013)

Czechoslovak Mathematical Journal

Similarity:

An edge e of a k -connected graph G is said to be k -removable if G - e is still k -connected. A subgraph H of a k -connected graph is said to be k -contractible if its contraction results still in a k -connected graph. A k -connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k -connected. In this paper, we show that there is a contractible subgraph in a 5 -connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex...

Join of two graphs admits a nowhere-zero 3 -flow

Saieed Akbari, Maryam Aliakbarpour, Naryam Ghanbari, Emisa Nategh, Hossein Shahmohamad (2014)

Czechoslovak Mathematical Journal

Similarity:

Let G be a graph, and λ the smallest integer for which G has a nowhere-zero λ -flow, i.e., an integer λ for which G admits a nowhere-zero λ -flow, but it does not admit a ( λ - 1 ) -flow. We denote the minimum flow number of G by Λ ( G ) . In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ ( G ∨ H ) ≤ 3 except two cases: (i) One of the graphs G and H is K 2 and the other is 1 -regular. (ii) H = K 1 and G is a graph with at least one isolated vertex or a component whose every...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by γ r ( G ) , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then γ r ( U ) ≥ ⎡ n / 3 ⎤ , and provide a characterization of graphs achieving this bound.

On ( 4 , 1 ) * -choosability of toroidal graphs without chordal 7-cycles and adjacent 4-cycles

Haihui Zhang (2013)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

A graph G is called ( k , d ) * -choosable if for every list assignment L satisfying | L ( v ) | = k for all v ∈ V ( G ) , there is an L -coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. In this paper, it is proved that every toroidal graph without chordal 7-cycles and adjacent 4-cycles is ( 4 , 1 ) * -choosable.

Digraphs with isomorphic underlying and domination graphs: connected U G c ( d )

Kim A.S. Factor, Larry J. Langley (2007)

Discussiones Mathematicae Graph Theory

Similarity:

The domination graph of a directed graph has an edge between vertices x and y provided either (x,z) or (y,z) is an arc for every vertex z distinct from x and y. We consider directed graphs D for which the domination graph of D is isomorphic to the underlying graph of D. We demonstrate that the complement of the underlying graph must have k connected components isomorphic to complete graphs, paths, or cycles. A complete characterization of directed graphs where k = 1 is presented. ...

On well-covered graphs of odd girth 7 or greater

Bert Randerath, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth...

The structure and existence of 2-factors in iterated line graphs

Michael Ferrara, Ronald J. Gould, Stephen G. Hartke (2007)

Discussiones Mathematicae Graph Theory

Similarity:

We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where L k ( G ) contains a 2-factor.