Results 1 to 10 of about 10,088 (246)
Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs
Discussiones Mathematicae Graph Theory, 2022 A graph G is called Hamilton-connected if for every pair of distinct vertices {u, v} of G there exists a Hamilton path in G that connects u and v. A graph G is said to be t-tough if t·ω(G − X) ≤ |X| for all X ⊆ V (G) with ω(G − X) > 1. The toughness of G,
Zheng Wei, Broersma Hajo, Wang Ligong
doaj +3 more sources
Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
Discussiones Mathematicae Graph Theory, 2016 A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general.
Li Binlong +2 more
doaj +2 more sources
Forbidden Subgraphs for Existences of (Connected) 2-Factors of a Graph
Discussiones Mathematicae Graph Theory, 2023 Clearly, having a 2-factor in a graph is a necessary condition for a graph to be hamiltonian, while having an even factor in graph is a necessary condition for a graph to have a 2-factor.
Yang Xiaojing, Xiong Liming
doaj +1 more source
Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs
Discussiones Mathematicae Graph Theory, 2022 In this paper, we completely characterize the connected forbidden subgraphs and pairs of connected forbidden subgraphs that force a 2-edge-connected (2-connected) graph to be collapsible.
Liu Xia, Xiong Liming
doaj +1 more source
Discussiones Mathematicae Graph Theory, 2022 A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the ...
Yang Xiaojing, Xiong Liming
doaj +1 more source
Tree in forbidden triples generating a finite set of graphs with high connectivity
AKCE International Journal of Graphs and Combinatorics, 2020 For a graph and a set of connected graphs, is said be -free if does not contain any member of as an induced subgraph. For , we let denote the set of all -connected -free graphs.
Yoshimi Egawa, Zhixian Zhao
doaj +1 more source
Paw-Type Characterization of Hourglass-Free Hamilton-Connected Graphs
Axioms, 2023 This paper introduces the forbidden subgraph conditions for Hamilton-connected graphs. If the degree sequence of the graph is (4,2,2,2,2) and it is connected, then it is called hourglassΓ0.
Panpan Wang, Liming Xiong
doaj +1 more source
Axioms, 2022 Let H be a class of given graphs. A graph G is said to be H-free if G contains no induced copies of H for any H∈H. In this article, we characterize all connected subgraph pairs {R,S} guranteeing the edge-connectivity of a connected {R,S}-free graph to ...
Junfeng Du, Ziwen Huang, Liming Xiong
doaj +1 more source
Quantum query complexity of minor-closed graph properties [PDF]
, 2011 We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether an $n$-vertex graph is planar, is a forest, or does not contain a path of a given length. We show that most minor-closed properties-
Childs, Andrew M., Kothari, Robin
core +5 more sources
Upward-closed hereditary families in the dominance order [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 The majorization relation orders the degree sequences of simple graphs into posets called dominance orders. As shown by Ruch and Gutman (1979) and Merris (2002), the degree sequences of threshold and split graphs form upward-closed sets within the ...
Michael D. Barrus, Jean A. Guillaume
doaj +1 more source