Results 71 to 80 of about 312 (179)
Spanning Plane Subgraphs of 1‐Plane Graphs
Journal of Graph Theory, Volume 110, Issue 3, Page 290-297, November 2025.ABSTRACT A graph drawn on the plane is called 1‐plane if each edge is crossed at most once by another edge. In this paper, we show that every 4‐edge‐connected 1‐plane graph has a connected spanning plane subgraph. We also show that there exist infinitely many 4‐connected 1‐plane graphs that have no 2‐connected spanning plane subgraphs.
Kenta Noguchi +2 more
wiley +1 more source
Computer-Aided Civil and Infrastructure Engineering, Volume 40, Issue 28, Page 5325-5350, 28 November 2025.Abstract Road networks face increasing disruptions, yet vulnerability assessment methods either oversimplify traffic dynamics or require extensive computational simulations. This research introduces a novel approach integrating traffic simulation, graph theory, and machine learning for efficient and accurate vulnerability assessment.
Abdel Rahman Marian +2 more
wiley +1 more source
Indiscernibles in monadically NIP theories
Bulletin of the London Mathematical Society, Volume 57, Issue 11, Page 3326-3345, November 2025.Abstract We prove various results around indiscernibles in monadically NIP theories. First, we provide several characterizations of monadic NIP in terms of indiscernibles, mirroring previous characterizations in terms of the behavior of finite satisfiability. Second, we study (monadic) distality in hereditary classes and complete theories.
Samuel Braunfeld, Michael C. Laskowski
wiley +1 more source
An Implicit Enumeration Approach for Maximum Ratio Clique Relaxations
Networks, Volume 86, Issue 3, Page 241-262, October 2025.ABSTRACT This article proposes an implicit enumeration approach to solve the maximum ratio s$$ s $$‐plex and the maximum ratio s$$ s $$‐defective clique problems. The approach is inspired by the classical Bron‐Kerbosch algorithm for enumerating all maximal cliques in a graph, which is extended to enumerating structures that are hereditary on induced ...
Yehor Blokhin +4 more
wiley +1 more source
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 +1 more source
Longest cycles in vertex‐transitive and highly connected graphs
Bulletin of the London Mathematical Society, Volume 57, Issue 10, Page 2975-2990, October 2025.Abstract We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lovász from 1969 and Thomassen from 1978, respectively, states that all connected vertex‐transitive graphs contain a Hamiltonian path, and that all sufficiently large such graphs even contain a Hamiltonian cycle.
Carla Groenland +4 more
wiley +1 more source
Complexity Framework for Forbidden Subgraphs
, 2022 For any finite set H={H1,…,Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,…,Hp as a subgraph. Similar to known meta-classifications for the minor and topological minor relations, we give a meta-classification for the subgraph relation.
Johnson, Matthew S. +6 more
openaire +2 more sources
Tight bounds for intersection‐reverse sequences, edge‐ordered graphs, and applications
Journal of the London Mathematical Society, Volume 112, Issue 4, October 2025.Abstract In 2006, Marcus and Tardos proved that if A1,⋯,An$A^1,\dots,A^n$ are cyclic orders on some subsets of a set of n$n$ symbols such that the common elements of any two distinct orders Ai$A^i$ and Aj$A^j$ appear in reversed cyclic order in Ai$A^i$ and Aj$A^j$, then ∑i|Ai|=O(n3/2logn)$\sum _{i} |A^i|=O(n^{3/2}\log n)$.
Barnabás Janzer +3 more
wiley +1 more source
Rainbow connection and forbidden subgraphs
Discrete Mathematics, 2015 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Holub, Přemysl +3 more
openaire +1 more source
Domination in graphoidally covered graphs: Least-kernel graphoidal graphs-II
AKCE International Journal of Graphs and Combinatorics, 2018 Given a graph , not necessarily finite, a graphoidal cover of means a collection of non-trivial paths in called -edges, which are not necessarily open (not necessarily finite), such that every vertex of is an internal vertex of at most one path in and ...
Purnima Gupta, Rajesh Singh
doaj +2 more sources