Displaying similar documents to “The diameter of paired-domination vertex critical graphs”

Some Toughness Results in Independent Domination Critical Graphs

Nawarat Ananchuen, Watcharaphong Ananchuen (2015)

Discussiones Mathematicae Graph Theory

Similarity:

A subset S of V (G) is an independent dominating set of G if S is independent and each vertex of G is either in S or adjacent to some vertex of S. Let i(G) denote the minimum cardinality of an independent dominating set of G. A graph G is k-i-critical if i(G) = k, but i(G+uv) < k for any pair of non-adjacent vertices u and v of G. In this paper, we establish that if G is a connected 3-i-critical graph and S is a vertex cutset of G with |S| ≥ 3, then [...] improving a result proved...

The eavesdropping number of a graph

Jeffrey L. Stuart (2009)

Czechoslovak Mathematical Journal

Similarity:

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v , a minimum { u , v } -separating set is a smallest set of edges in G whose removal disconnects u and v . The edge connectivity of G , denoted λ ( G ) , is defined to be the minimum cardinality of a minimum { u , v } -separating set as u and v range over all pairs of distinct vertices in G . We introduce and investigate the eavesdropping number, denoted ε ( G ) , which is defined to be the maximum cardinality...

The Connectivity Of Domination Dot-Critical Graphs With No Critical Vertices

Michitaka Furuya (2014)

Discussiones Mathematicae Graph Theory

Similarity:

An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and k(G) = 1. In this...

Radius-invariant graphs

Vojtech Bálint, Ondrej Vacek (2004)

Mathematica Bohemica

Similarity:

The eccentricity e ( v ) of a vertex v is defined as the distance to a farthest vertex from v . The radius of a graph G is defined as a r ( G ) = min u ∈ V ( G ) { e ( u ) } . A graph G is radius-edge-invariant if r ( G - e ) = r ( G ) for every e ∈ E ( G ) , radius-vertex-invariant if r ( G - v ) = r ( G ) for every v ∈ V ( G ) and radius-adding-invariant if r ( G + e ) = r ( G ) for every e ∈ E ( G ¯ ) . Such classes of graphs are studied in this paper.