Some Theorems on Abstract Graphs

1952/01/01 by G. A. Dirac · 1,601 citations
Mathematics · Physics and Astronomy · #Citation #Combinatorics #Computer science #Dirac (video compression format) #Library science #Mathematics #Physics #Quantum Mechanics and Applications #Quantum mechanics

paper · doi:10.1112/plms/s3-2.1.69

published in Proceedings of the London Mathematical Society s3-2(1), 69-81 (Wiley)

openalex publication_date 1952/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Cited by

• Robustness and hyperstability for the Erdős-Gallai theorem
• Hamiltonian cycles in 7-tough (P₄∪ P₁)-free graphs
• Breaking the Bollobás-Eldridge-Catlin Barrier for Bipartite Graphs
• Perfect matching in 4-partite 4-uniform hypergraphs
• Disjoint cycles covering specified vertices in bipartite graphs with partial degrees
• A Simple Extension of Dirac's Theorem on Hamiltonicity
• Multicolor Gallai-Ramsey numbers of C₉ and C₁₁
• Spanning trees in randomly perturbed graphs
• Exact results on generalized Erdős-Gallai problems
• Combinatorial theorems relative to a random set
• Sharp Diagonal Thresholds for Tight Hamilton Cycles in Uniformly Dense 3-Graphs
• Variants of Baranyai's Theorem with Additional Conditions
• Semi-Degree Condition for Arbitrary H-Linked Oriented Graphs
• Cycle lengths and minimum degree of graphs
• On graphs whose cycle space is spanned by their Hamilton cycles
• A Rainbow Dirac's Theorem
• Clique factors in random samplings of regular graphs
• Verifying Hadwiger's Conjecture for Examples of Graphs with α(G) = 2
• Transversal Hamilton Paths and Cycles
• The maximum number of perfect matchings of semi-regular graphs
• Toughness and Vertex Degrees
• A Common Generalization of Dirac's two Theorems
• Bootstrap percolation in Ore-type graphs
• Anti-Ramsey Number of Stars in 3-uniform hypergraphs
• Loose Hamiltonicity
• The k-proper index of complete bipartite and complete multipartite graphs
• On the Hypergraph Nash-Williams' Conjecture
• On Posa's conjecture for random graphs
• Ore's Conjecture on color-critical graphs is almost true
• Ore‐type degree conditions for a graph to be H‐linked
• Clique factors in Kneser graphs
• Extending two results on hamiltonian graphs involving the bipartite-hole-number
• Hamiltonicity in randomly perturbed hypergraphs
• Some sufficient conditions on Hamiltonian digraph
• Fractional matching number and spectral radius of nonnegative matrix of graphs
• A Note on Hamilton Cycles
• Mader's Conjecture and Its Variants for Cographs
• The n-queens problem
• Rainbow matchings in edge-colored graphs
• Chords of longest cycles in graphs with large circumferences
• Bipartite holes, degree sums and Hamilton cycles
• Robustness for expander graphs
• The circumference of a graph with given minimum degree and clique number
• Tree decompositions of graphs without large bipartite holes
• The maximum size of a graph with prescribed order, circumference and minimum degree
• A Polynomial time Algorithm for 3SAT
• Doubly Stochastic Subspace Clustering
• Large Y_k,b -tilings and Hamilton ℓ -cycles in k-uniform hypergraphs
• Hamilton cycles in quasirandom hypergraphs
• Counting Hamiltonian Cycles in Dirac Hypergraphs
• Inverse Turán numbers
• Dirac's Condition for Spanning Halin Subgraphs
• Hamiltonian cycles in Cayley graphs of imprimitive complex reflection groups
• A stability version for a theorem of Erdős on nonhamiltonian graphs
• A Note on Minimum Degree Condition for Hamiltonian (a,b)-Cycles in Hypergraphs
• Stability in the Erdos--Gallai Theorem on cycles and paths
• Transversal Hamilton Cycle in Hypergraph Systems
• Universality for transversal powers of Hamilton cycles
• Spanning trees with large maximum degrees
• A survey on Hamilton cycles in directed graphs
• Fractional Clique Decompositions of Dense Hypergraphs
• Worst-case time decremental connectivity and k-edge witness
• The Ramsey number of a long even cycle versus a star
• Ramsey numbers of long even cycles versus books
• Radio gracefulness of Moore graphs and beyond
• Robust hamiltonicity of random directed graphs
• Maxima of the Q-index: forbidden even cycles
• Graph Invariants and Large Cycles - a Catalog of Pure Links
• On the pancyclicity of 2-connected [5,3]-graphs
• The exact total degree threshold for the square of a Hamilton cycle in digraphs
• Cycle Extendability of Hamiltonian Strongly Chordal Graphs
• Long Cycles in 1-tough Graphs
• From finding a spanning subgraph H to an H-factor
• Colour-biased Hamilton cycles in dense graphs and random graphs
• Clique-factors in graphs with low K_ℓ-independence number
• The Ramsey number of mixed-parity cycles III
• K_r-Factors in Graphs with Low Independence Number
• Maxima Q-index of graphs with forbidden odd cycles
• New Perspectives on Neighborhood-Prime Labelings of Graphs
• Beyond Hamiltonicity of Prime Difference Graphs
• Longest odd cycles in non-bipartite C_2k+1-free graphs
• Upper Bounds for the Number of Hamiltonian Cycles
• Powers of paths in tournaments
• A note on a degree sum condition for long cycles in graphs
• Perturbation of dense graphs
• Long paths and cycles in subgraphs of the cube
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• The Cycle-Complete graph Ramsey numbers
• Perfect tilings with the generalised triangle in k-graphs
• Hamilton cycles in highly connected and expanding graphs
• Generalized Turán number for linear forests
• Extensions of a theorem of Erdős on nonhamiltonian graphs
• Rainbow structures in a collection of graphs with degree conditions
• Global cycle properties in locally isometric graphs
• On vertex-disjoint paths in regular graphs
• On extremal hypergraphs for hamiltonian cycles
• Cyclic subsets of tournaments
• Random directed graphs are robustly Hamiltonian
• Erdős meets Nash-Williams
• Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions
• On Hamiltonian Berge cycles in 3-uniform hypergraphs
• Large book--cycle Ramsey numbers
• Local Connectivity, Local Degree Conditions, some Forbidden Induced Subgraphs, and Cycle Extendability
• New bounds for linear arboricity and related problems
• F-factors in hypergraphs via absorption
• SFCM-R: A novel algorithm for the hamiltonian sequence problem
• A note on eigenvalues and Hamiltoinan properties of k-connected graphs
• On k-ended spanning and dominating trees
• Monochromatic cycles and the monochromatic circumference in 2-coloured graphs
• Resilience for tight Hamiltonicity
• Relative Length of Long Paths and Cycles in Graphs
• Positional games on randomly perturbed graphs
• Hat guessing number and guaranteed subgraphs
• Corrádi and Hajnal's theorem for sparse random graphs
• Optimal stability results on color-biased Hamilton cycles
• Color-Critical Graphs Have Logarithmic Circumference
• Hamiltonicity of 3-tough (K₂ ∪ 3K₁)-free graphs
• Combined degree and connectivity conditions for H-linked graphs
• On star-wheel Ramsey numbers
• Transversal packings in families of percolated hypergraphs
• Cycles and paths through vertices whose degrees are at least the bipartite-hole-number
• Hamilton cycles, minimum degree and bipartite holes
• Regular Graphs of High Degree are 1-Factorizable
• New Ore-type Conditions for Hamilton Cycles and Spanning Trees with few leaves
• Almost partitioning the hypercube into copies of a graph
• Local resilience of an almost spanning k-cycle in random graphs
• A Survey of Best Monotone Degree Conditions for Graph Properties
• On Dirac's Conjecture
• Signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree
• Gallai-Ramsey number for the union of stars
• On the circumference, connectivity and dominating cycles
• A note on the Ramsey number of even wheels versus stars
• Total coloring graphs with large minimum degree
• The Hamilton cycle space of random regular graphs and randomly perturbed graphs
• An exact Ore-degree condition for Hamilton cycles in oriented graphs
• A note on finding long directed cycles above the minimum degree bound in 2-connected digraphs
• Robustness of the Sauer-Spencer Theorem
• Packing and counting arbitrary Hamilton cycles in random digraphs
• My Research Visiting Card in Hamiltonian Graph Theory
• New Tests of Randomness for Circular Data
• Hamilton cycles in regular graphs perturbed by a random 2-factor
• Spanning embeddings of arrangeable graphs with sublinear bandwidth
• Cycle lengths in the percolated hypercube
• Matchings and Hamilton Cycles with Constraints on Sets of Edges
• On directed version of the Sauer-Spender Theorem
• Packing tetrahedrons in edge-weighted graphs
• Hamilton cycles in tough (2P₂ ∪ P₁)-free graphs
• Antidirected paths in oriented graphs
• Balanced Spanning Caterpillars
• A Lower Bound for the Circumference Involving Connectivity
• Universality for transversal Hamilton cycles in random graphs
• Perfect tilings of 3-graphs with the generalised triangle
• Rainbow Hamilton cycles in randomly coloured randomly perturbed dense graphs
• The detour covering number and cummerbund covering number of a graph
• A semi-exact degree condition for Hamilton cycles in digraphs
• Extremal Theta-free planar graphs
• A Fan-type condition involving bipartite independence number for hamiltonicity in graphs
• A variation of a theorem by Pósa
• Packing, Counting and Covering Hamilton cycles in random directed graphs
• Improved Upper Bounds for Gallai-Ramsey Numbers of Odd Cycles
• Gallai-Ramsey numbers of odd cycles
• Embedding degenerate graphs of small bandwidth
• k-Critical Graphs in P₅-Free Graphs
• On some Versions of Conjectures of Bondy and Jung
• A sufficient condition for the existence of an anti-directed 2-factor in a directed graph
• Gallai Ramsey number for double stars
• From a Consequence of Bertrand's Postulate to Hamilton Cycles
• Minimum degree of 3-graphs without long linear paths
• An Ore-type theorem for [3]-graphs
• Theory: Multidimensional Space of Events
• Positive codegree thresholds for Hamilton cycles in hypergraphs
• Counting Cycles in Graphs with Bounded Circumference
• Cyclability of id-cycles in graphs
• Perfect matching in 3-uniform hypergraphs with large vertex degree
• A degree sum condition on the order, the connectivity and the independence number for Hamiltonicity
• On exactness of SDP relaxation for the maximum cut problem
• On the structure of random graphs with constant r-balls
• Maxima of the Q-index: graphs without long paths
• Simple Proofs of two Dirac-type Theorems Involving Connectivity
• An extremal problem for H‐linked graphs
• Triangle packings and 1-factors in oriented graphs
• Minimum degree thresholds for bipartite graph tiling
• Fast probabilistic algorithms for hamiltonian circuits and matchings
• Proof of the Seymour conjecture for large graphs
• Dirac's theorem for random graphs
• Finding Perfect Matchings in Bipartite Hypergraphs
• Selecting and covering colored points
• Pancyclicity in hypergraphs with large uniformity
• Ore-degree threshold for the square of a Hamiltonian cycle
• A method in graph theory
• Non-commuting graphs of projective spaces over central quotients of Lie algebras
• Spectral radius and Hamiltonicity of uniform hypergraphs
• On path-quasar Ramsey numbers
• Transversal Hamilton cycle in hypergraph systems
• Polynomial-time perfect matchings in dense hypergraphs
• Dacey Graphs
• The Regularity Lemma and Its Applications in Graph Theory
• On chromatic number of graphs and set-systems
• The Hidden Algorithm of Ore's Theorem on Hamiltonian Cycles
• On the graph structure of convex polyhedra in n -space
• A stability theorem for Berge Hamiltonian cycles under a minimum degree condition
• Branch-depth: Generalizing tree-depth of graphs
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY
• Polynomial-time perfect matchings in dense hypergraphs
• A localization method in Hamiltonian graph theory
• An Ore-type condition for hamiltonicity in graphs
• A study of two Ramsey numbers involving odd cycles
• Results and Problems on Equitable Coloring of Graphs
• Degree conditions restricted to induced paths for hamiltonicity of claw-heavy graphs
• Toughness in Graphs – A Survey
• Diameter Polytopes of Feasible Binary Programs
• On the Hamiltonicity of Triple Systems with High Minimum Degree
• Graph-Chromatic Implicit Relations
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• On end degrees and infinite cycles in locally finite graphs
• On the number of cliques in graphs with a forbidden subdivision or immersion
• Arbitrary orientations of cycles in oriented graphs
• Vertex pancyclic graphs
• On one extension of Dirac’s theorem on Hamiltonicity
• Efficient solution for finding Hamilton cycles in undirected graphs. [europepmc]
• A new algorithm to find fuzzy Hamilton cycle in a fuzzy network using adjacency matrix and minimum vertex degree. [europepmc]
• Microservice Security Framework for IoT by Mimic Defense Mechanism. [europepmc]