Results 1 to 10 of about 735 (221)
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 +5 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 +2 more sources
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
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
Classes of graphs with restricted interval models [PDF]
Discrete Mathematics & Theoretical Computer Science, 1999 We introduce q-proper interval graphs as interval graphs with interval models in which no interval is properly contained in more than q other intervals, and also provide a forbidden induced subgraph characterization of this class of graphs.
Andrzej Proskurowski, Jan Arne Telle
doaj +2 more sources
Forbidden subgraph pairs for traceability of block-chains
Electronic Journal of Graph Theory and Applications, 2013 A block-chain is a graph whose block graph is a path, i.e. it is either a $P_1$, a $P_2$, or a 2-connected graph, or a graph of connectivity 1 with exactly two end-blocks. A graph is called traceable if it contains a Hamilton path.
Binlong Li +2 more
doaj +1 more source