All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 7 Next

Displaying 121 – 140 of 667

Showing per page

Chvátal-Erdös type theorems

Jill R. Faudree, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Colton Magnant (2010)

Discussiones Mathematicae Graph Theory

The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1),...

Clique irreducibility of some iterative classes of graphs

Aparna Lakshmanan S., A. Vijayakumar (2008)

Discussiones Mathematicae Graph Theory

In this paper, two notions, the clique irreducibility and clique vertex irreducibility are discussed. A graph G is clique irreducible if every clique in G of size at least two, has an edge which does not lie in any other clique of G and it is clique vertex irreducible if every clique in G has a vertex which does not lie in any other clique of G. It is proved that L(G) is clique irreducible if and only if every triangle in G has a vertex of degree two. The conditions for the iterations of line graph,...

Connected domination critical graphs with respect to relative complements

Xue-Gang Chen, Liang Sun (2006)

Czechoslovak Mathematical Journal

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G . The minimum number of vertices in a connected dominating set of G is called the connected domination number of G , and is denoted by γ c ( G ) . Let G be a spanning subgraph of K s , s and let H be the complement of G relative to K s , s ; that is, K s , s = G ⊕ H is a factorization of K s , s . The graph G is k - γ c -critical relative to K s , s if γ c ( G ) = k and γ c ( G + e ) < k for each edge e ∈ E ( H ) . First, we discuss some classes of graphs whether they are γ c -critical relative...

Connected resolvability of graphs

Varaporn Saenpholphat, Ping Zhang (2003)

Czechoslovak Mathematical Journal

For an ordered set W = { w 1 , w 2 , ⋯ , w k } of vertices and a vertex v in a connected graph G , the representation of v with respect to W is the k -vector r ( v | W ) = ( d ( v , w 1 ) , d ( v , w 2 ) , ⋯ , d ( v , w k ) ) , where d ( x , y ) represents the distance between the vertices x and y . The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W . A resolving set for G containing a minimum number of vertices is a basis for G . The dimension dim ( G ) is the number of vertices in a basis for G . A resolving set W of G is connected if the subgraph...

Currently displaying 121 – 140 of 667