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

Michitaka Furuya

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

Displaying similar documents to “The Connectivity Of Domination Dot-Critical Graphs With No Critical Vertices”

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...

On cotree-critical and DFS cotree-critical graphs.

de Fraysseix, Hubert, Ossona de Mendez, Patrice (2003)

Journal of Graph Algorithms and Applications

Similarity:

A characterization of diameter-2-critical graphs with no antihole of length four

Teresa Haynes, Michael Henning (2012)

Open Mathematics

Similarity:

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As...

The diameter of paired-domination vertex critical graphs

Michael A. Henning, Christina M. Mynhardt (2008)

Czechoslovak Mathematical Journal

Similarity:

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks (1998), 199–206). A paired-dominating set of a graph $G$ with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of $G$ , denoted by $γ_{pr} (G)$ , is the minimum cardinality of a paired-dominating set of $G$ . The graph $G$ is paired-domination vertex critical if for every vertex $v$ of $G$ that is not adjacent to a vertex of...

On the Independence Number of Edge Chromatic Critical Graphs

Shiyou Pang, Lianying Miao, Wenyao Song, Zhengke Miao (2014)

Discussiones Mathematicae Graph Theory

Similarity:

In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤ [...] . It is known that α (G) < [...] |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤ [...] |V | when △ ≥ 5 and n2 ≤ 2(△− 1)

Partition numbers, connectivity and Hamiltonicity

Mieczysław Borowiecki (1987)

Časopis pro pěstování matematiky

Similarity:

Generalized matrix graphs and completely independent critical cliques in any dimension

John J. Lattanzio, Quan Zheng (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For natural numbers k and n, where 2 ≤ k ≤ n, the vertices of a graph are labeled using the elements of the k-fold Cartesian product Iₙ × Iₙ × ... × Iₙ. Two particular graph constructions will be given and the graphs so constructed are called generalized matrix graphs. Properties of generalized matrix graphs are determined and their application to completely independent critical cliques is investigated. It is shown that there exists a vertex critical graph which admits a family of k...

Total domination edge critical graphs with maximum diameter

Lucas C. van der Merwe, Cristine M. Mynhardt, Teresa W. Haynes (2001)

Discussiones Mathematicae Graph Theory

Similarity:

Denote the total domination number of a graph G by γₜ(G). A graph G is said to be total domination edge critical, or simply γₜ-critical, if γₜ(G+e) < γₜ(G) for each edge e ∈ E(G̅). For 3ₜ-critical graphs G, that is, γₜ-critical graphs with γₜ(G) = 3, the diameter of G is either 2 or 3. We characterise the 3ₜ-critical graphs G with diam G = 3.

A maximum degree theorem for diameter-2-critical graphs

Teresa Haynes, Michael Henning, Lucas Merwe, Anders Yeo (2014)

Open Mathematics

Similarity:

A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where...