Results 81 to 90 of about 10,088 (246)

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, Sean Longbrake, Raphael Steiner, Jérémie Turcotte, Liana Yepremyan   +4 more
wiley   +1 more source

Apex Graphs and Cographs

Theory and Applications of Graphs
A class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G.
Jagdeep Singh, Vaidy Sivaraman, Thomas Zaslavsky   +2 more
doaj   +1 more source

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, Oliver Janzer, Abhishek Methuku, Gábor Tardos   +3 more
wiley   +1 more source

Forbidden Pairs and (k,m)-Pancyclicity

Discussiones Mathematicae Graph Theory, 2017
A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . . , n}.
Crane Charles Brian
doaj   +1 more source

Small clique number graphs with three trivial critical ideals [PDF]

, 2013
The critical ideals of a graph are the determinantal ideals of the generalized Laplacian matrix associated to a graph. In this article we provide a set of minimal forbidden graphs for the set of graphs with at most three trivial critical ideals.
Carlos, Carlos A. Alfaro, E. Valencia
core  

Crossing estimates for the Ising model on general s‐embeddings

Proceedings of the London Mathematical Society, Volume 131, Issue 4, October 2025.
Abstract We prove Russo–Seymour–Welsh‐type crossing estimates for the FK–Ising model on general s‐embeddings whose origami map has an asymptotic Lipschitz constant strictly smaller than 1, provided it satisfies a mild non‐degeneracy assumption. This result extends the work of Chelkak and provides a general framework to prove that the usual connection ...
Rémy Mahfouf
wiley   +1 more source

Bounded Search Tree Algorithms for Parameterized Cograph Deletion: Efficient Branching Rules by Exploiting Structures of Special Graph Classes

, 2010
Many fixed-parameter tractable algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingly complex case analysis.
A. Cournier, B. Jamison, D. Coppersmith, D. Kratsch, D. Lokshtanov, D. Seinsche, D.G. Corneil, H. Kaplan, J. Gramm, J. Guo, J.-H. Yan, J.-L. Fouquet, L. Cai, M. Yannakakis, R. Niedermeier, R.E. Tarjan, R.M. McConnell, S.D. Nikolopoulos   +17 more
core   +1 more source

Line Graphs and Forbidden Induced Subgraphs

Journal of Combinatorial Theory, Series B, 2001
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Hong-Jian Lai, Lubomír Soltés
openaire   +2 more sources

Weighted Turán Theorems With Applications to Ramsey‐Turán Type of Problems

Journal of Graph Theory, Volume 110, Issue 1, Page 59-71, September 2025.
ABSTRACT We study extensions of Turán Theorem in edge‐weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique containing it. These problems are motivated by Ramsey‐Turán type problems.
József Balogh, Domagoj Bradač, Bernard Lidický   +2 more
wiley   +1 more source

Ramsey-type Theorems with Forbidden Subgraphs [PDF]

Combinatorica, 2001
P. Erdős and A. Hajnal conjectured that for every finite graph \(H\) every \(H\)-free graph on \(n\) vertices contains a complete or empty subgraph of size \(n^{\varepsilon(H)}\). It is shown that if the conjecture holds for \(H_1\), \(H_2\) then it holds for the graph which is \(H_1\) with one vertex blown up to a copy of \(H_2\).
János Pach, Noga Alon, József Solymosi
openaire   +2 more sources