Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs
View through CrossRef
AbstractLet γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k−1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k−1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.
Title: Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs
Description:
AbstractLet γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k−1.
In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D.
Sumner cites a conjecture of E.
Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.
e.
, for any k ≥ 4), (k−1)‐connected, k‐edge‐critical graphs are Hamiltonian.
” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs.
© 2005 Wiley Periodicals, Inc.
Related Results
The upper connected edge geodetic number of a graph
The upper connected edge geodetic number of a graph
For a non-trivial connected graph G, a set S ? V (G) is called an edge
geodetic set of G if every edge of G is contained in a geodesic joining some
pair of vertices in S. The...
2-Edge Connectivity in Directed Graphs
2-Edge Connectivity in Directed Graphs
Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly, not much has been inv...
The edge-to-edge geodetic domination number of a graph
The edge-to-edge geodetic domination number of a graph
Let G = (V, E) be a connected graph with at least three vertices. A set S Í E is called an edge-to-edge geodetic dominating set of G if S is both an edge-to-edge geodetic set of G ...
THE FORCING EDGE FIXING EDGE-TO-VERTEX MONOPHONIC NUMBER OF A GRAPH
THE FORCING EDGE FIXING EDGE-TO-VERTEX MONOPHONIC NUMBER OF A GRAPH
For a connected graph G = (V, E), a set Se ⊆ E(G)–{e} is called an edge fixing edge-to-vertex monophonic set of an edge e of a connected graph G if every vertex of G lies on an e –...
The Restricted Edge-Connectivity of Strong Product Graphs
The Restricted Edge-Connectivity of Strong Product Graphs
The restricted edge-connectivity of a connected graph G, denoted by λ′(G), if it exists, is the minimum cardinality of a set of edges whose deletion makes G disconnected, and each ...
Edge Fault-Tolerant Strong Menger Edge Connectivity of Folded Crossed Cubes
Edge Fault-Tolerant Strong Menger Edge Connectivity of Folded Crossed Cubes
A graph is called strongly Menger-edge connected (SME-connected) if any two vertices are connected by as many edge-disjoint paths as their smaller degree. For positive integers t a...
Twilight graphs
Twilight graphs
AbstractThis paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite:(a) there is an ...
Finding the closed-form solutions of dissipative oscillatory systems
Finding the closed-form solutions of dissipative oscillatory systems
AbstractThis paper shows how to use the approximate Hamiltonian approach for the non-conservative system not capable of possessing Hamiltonian. Using the approximate Hamiltonian me...