On maximal paths and circuits of graphs
From MaRDI portal
Publication:3265306
DOI10.1007/BF02024498zbMath0090.39401OpenAlexW1996106086WikidataQ105583464 ScholiaQ105583464MaRDI QIDQ3265306
Publication date: 1959
Published in: Acta Mathematica Academiae Scientiarum Hungaricae (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02024498
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)
Related Items
On the optimality of Bellman-Ford-Moore shortest path algorithm, On some three-color Ramsey numbers for paths, Extension of paths and cycles for hypergraphs, Longest paths joining given vertices in a graph, On fan-wheel and tree-wheel Ramsey numbers, All Ramsey numbers for brooms in graphs, The multicolour Ramsey number of a long odd cycle, Tight cycles in hypergraphs, Small topological complete subgraphs of ``dense graphs, Graph saturation games, Stability in the Erdős-Gallai theorems on cycles and paths, An improved bound for the monochromatic cycle partition number, Eigenvalues and forbidden subgraphs. I., Rainbow generalizations of Ramsey theory: A survey, A new class of Ramsey-Turán problems, Large circuits in binary matroids of large cogirth. I, Improved bounds for Erdős' matching conjecture, On the minimal length of the longest trail in a fixed edge-density graph, On the Erdős-Sós conjecture for graphs having no path with \(k+4\) vertices, Anti-Ramsey number of matchings in hypergraphs, On the Turán number of forests, Exact solution of the hypergraph Turán problem for \(k\)-uniform linear paths, Rainbow numbers for matchings in plane triangulations, Hypergraphs with no cycle of length 4, The extremal function for partial bipartite tilings, Three results on cycle-wheel Ramsey numbers, On path-coverings and Hamilton-connectivity of finite graphs, Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels, A Dirac theorem for trestles, Rainbow cycles in edge-colored graphs, Dense arbitrarily partitionable graphs, An Erdős-Gallai theorem for matroids, Maximale Kreise in Graphen, Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees, Parallel realization of permutations over trees, 3-uniform hypergraphs avoiding a given odd cycle, Some asymptotic ith Ramsey numbers, A generalization of Menger's theorem, Corrigendum to ``Maxima of the \(Q\)-index: forbidden odd cycles, Turán problems and shadows. I: Paths and cycles, Edge-colorings of uniform hypergraphs avoiding monochromatic matchings, Vertex coverings by monochromatic cycles and trees, Spanning trees: A survey, Turán numbers for disjoint copies of graphs, On a generalization of a theorem of Nash-Williams, Partitioning 2-edge-colored graphs by monochromatic paths and cycles, Cycles in weighted graphs, Coverings by few monochromatic pieces: a transition between two Ramsey problems, The Ramsey numbers of paths versus wheels: a complete solution, Rainbow matchings in properly-colored hypergraphs, On the rainbow Turán number of paths, Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\), Improved bounds on the multicolor Ramsey numbers of paths and even cycles, Pentagons vs. triangles, Connected graphs without long paths, Long paths with endpoints in given vertex-subsets of graphs, Rainbow Turán problems for paths and forests of stars, Tight cycles and regular slices in dense hypergraphs, On the maximum number of edges in a hypergraph with given matching number, On 3-uniform hypergraphs without a cycle of a given length, Extremal problems involving vertices and edges on odd cycles, The spectral radius of graphs without paths and cycles of specified length, Some remarks on long monochromatic cycles in edge-colored complete graphs, Graph invariants and large cycles: a survey, All Ramsey numbers for cycles in graphs, A sufficient degree condition for a graph to contain all trees of size \(k\), On maximal circuits in directed graphs, Cycles in 2-connected graphs, Alternating Hamiltonian cycles, Développements recents de la théorie des graphes, Generalized Ramsey theory for multiple colors, A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs, Equipartite colorings in graphs and hypergraphs, On the maximum size of connected hypergraphs without a path of given length, Extremal \(G\)-free induced subgraphs of Kneser graphs, The maximum number of \(K_j\)-subgraphs in a graph with \(k\) independent edges, The Turán number of the graph \(2P_5\), Ramsey numbers of trees versus odd cycles, On the multi-colored Ramsey numbers of paths and even cycles, Some three-color Ramsey numbers, \(R(P_4,P_5,C_k)\) and \(R(P_4,P_6,C_k)\), Hypergraph extensions of the Erdős-Gallai theorem, Invitation to intersection problems for finite sets, Degree powers in \(C_5\)-free graphs, Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey, Long cycles and the codiameter of a graph. I, Complete solution for the rainbow numbers of matchings, A theorem on cycle-wheel Ramsey number, A variation of a conjecture due to Erdös and Sós, A two-person game on graphs where each player tries to encircle his opponent's men, On an extremal problem in graph theory., Minimum degree of 3-graphs without long linear paths, Berge cycles in non-uniform hypergraphs, Homomorphism thresholds for odd cycles, Stability results on the circumference of a graph, An Ore-type condition for the existence of two disjoint cycles, On restricted colourings of \(K_ n\), A generalization of Dirac's theorem, Asymptotic solution for a new class of forbidden r-graphs, Families of finite sets in which no set is covered by the union of \(r\) others, The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs, Spectral conditions for traceability of connected claw-free graphs, Hypergraph Extensions of the Erdős-Gallai Theorem, Monochromatic Cycles in 2-Coloured Graphs, On the Maximum Number of Edges in a Triple System Not Containing a Disjoint Family of a Given Size, The Maximum Number of Triangles in C2k+1-Free Graphs, Hypergraphs with No Cycle of a Given Length, Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size, Nearly-Regular Hypergraphs and Saturation of Berge Stars, On the Erdős–Sós conjecture for trees with bounded degree, Powers of paths in tournaments, Rainbow version of the Erdős Matching Conjecture via concentration, The Size of a Hypergraph and its Matching Number, A Stability Result on Matchings in 3-Uniform Hypergraphs, Flots et tensions dans un graphe, Perfect Matchings in Hypergraphs and the Erdös Matching Conjecture, RAMSEY NUMBERS FOR TREES, A note on fractional covers of a graph, Counting H-free orientations of graphs, Monochromatic Cycle Partitions in Local Edge Colorings, Ramsey Size Linear Graphs, A note on the Tur\'an number of a Berge odd cycle, The Turán number of the graph 3P5, On Generalized Turán Results in Height Two Posets, Degree conditions and relative length of longest paths and cycles in graphs, Spectral extrema of graphs with bounded clique number and matching number, Anti‐Ramsey number of expansions of paths and cycles in uniform hypergraphs, Connectivity preserving trees in k‐connected or k‐edge‐connected graphs, A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs, Anti-Ramsey Number of Matchings in 3-Uniform Hypergraphs, Unavoidable chromatic patterns in 2‐colorings of the complete graph, Ordering \(Q\)-indices of graphs: given size and circumference, Outerplanar Turán numbers of cycles and paths, Turán numbers for disjoint paths, Extremal graphs for odd wheels, Extremal Problems for Hypergraph Blowups of Trees, Large simple \(d\)-cycles in simplicial complexes, Extremal Problem for Matchings and Rainbow Matchings on Direct Products, On families with bounded matching number, The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number, Exact bipartite Turán numbers of large even cycles, Improved bound on vertex degree version of Erdős matching conjecture, Large Yk,b ${Y}_{k,b}$‐tilings and Hamilton ℓ $\ell $‐cycles in k $k$‐uniform hypergraphs, A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs, Spectral radius and rainbow matchings of graphs, The k‐path vertex cover: General bounds and chordal graphs, Making an H $H$‐free graph k $k$‐colorable, Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result, A note on maximum size of a graph without isolated vertices under the given matching number, Stability version of Dirac's theorem and its applications for generalized Turán problems, Rainbow Turán numbers of matchings and forests of hyperstars in uniform hypergraphs, An \(A_\alpha\)-spectral Erdős-Pósa theorem, Extremal numbers of disjoint triangles in \(r\)-partite graphs, The Number of Cliques in Graphs Covered by Long Cycles, Maximum cliques in a graph without disjoint given subgraph, Cyclability, connectivity and circumference, On some Multicolor Ramsey Properties of Random Graphs, Monophonic convexity in weighted graphs, Extremal Numbers for Odd Cycles, On transit functions in weighted graphs, Extremal Results for Berge Hypergraphs, Paths and circuits in graphs: Extreme cases, Maximum cuts of graphs with forbidden cycles, Maximum and Minimum Degree Conditions for Embedding Trees, Going Far from Degeneracy, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, A Local Approach to the Erdös--Sós Conjecture, A Conjecture of Verstraëte on Vertex-Disjoint Cycles, Compact topological minors in graphs, Maximal circuits of graphs. I, Extensions of Turán's theorem on graphs, An Improved Bound for Vertex Partitions by Connected Monochromatic K-Regular Graphs, Unnamed Item, Unnamed Item, Generalized and geometric Ramsey numbers for cycles., A median-type condition for graph tiling, Spaces of \(p\)-vectors of bounded rank, On star-critical and upper size Ramsey numbers, The 3-Colour Ramsey Number of a 3-Uniform Berge Cycle, Long paths and cycles passing through specified vertices under the average degree condition, Many \(T\) copies in \(H\)-free graphs, Anti-Ramsey Numbers of Paths and Cycles in Hypergraphs, MAXIMUM CUTS IN GRAPHS WITHOUT WHEELS, Extensions of the Erdős–Gallai theorem and Luo’s theorem, The Turàn number of the graph 3P4, Coloring Powers and Girth, Spectral radius and Hamiltonian properties of graphs, Hypergraphs Not Containing a Tight Tree with a Bounded Trunk, Degree Conditions for Embedding Trees, Unnamed Item, Unnamed Item, Turán Numbers of Multiple Paths and Equibipartite Forests, The spectral radius of graphs without trees of diameter at most four, Avoiding long Berge cycles: the missing cases k = r + 1 and k = r + 2, On the multi-colored Ramsey numbers of cycles, Hypergraphs with no odd cycle of given length, Large Book-Cycle Ramsey Numbers, Cycle packing, Maximum bipartite subgraphs in $H$-free graphs, The Monochromatic Circumference of 2‐Edge‐Colored Graphs, Turán numbers for hypergraph star forests, The Turán numbers of special forests, Rainbow numbers for matchings and complete graphs, The Erdős-Sós conjecture for graphs whose complements contain no \(C_4\), Gaps in the saturation spectrum of trees, Edge-colorings avoiding a fixed matching with a prescribed color pattern, On three-color Ramsey numbers \(R(C_{4},K_{1,m},P_{n})\), Size and structure of large \((s,t)\)-union intersecting families, A note on the Turán number of an arbitrary star forest, Extremal graphs for the distinguishing index, The spectral radius of graphs with no intersecting odd cycles, Extremal graphs of the \(p\)th power of paths, Generalized rainbow Turán problems, Degree sums and spanning brooms of a graph, Generalized Turán number for linear forests, Partitioning complete bipartite graphs by monochromatic cycles, Two new sufficient conditions for Hamilton-connected graphs, Factorially many maximum matchings close to the Erdős-Gallai bound, Linear bounds for cycle-free saturation games, The Erdös-Sós conjecture for graphs without \(C_ 4\), Degree sum conditions on two disjoint cycles in graphs, Two vertex-disjoint cycles in a graph, On independent cycles and edges in graphs, Lagrangian densities of some sparse hypergraphs and Turán numbers of their extensions, The maximum number of cliques in graphs without long cycles, An Erdős-Gallai type theorem for uniform hypergraphs, Proof of the Erdős matching conjecture in a new range, The extremal graph problem of the icosahedron, Families with no matchings of size \(s\), New Ore's type results on hamiltonicity and existence of paths of given length in graphs, Ramsey numbers involving large dense graphs and bipartite Turán numbers, Graphs with large maximum degree containing no odd cycles of a given length, On completely positive graphs and their complements, Covering vertices of a graph by \(k\) disjoint cycles, A short proof of Erdős' conjecture for triple systems, Nearly bipartite graphs, Degree conditions for the existence of vertex-disjoint cycles and paths: a survey, Stability in the Erdős-Gallai theorem on cycles and paths. II, Some multicolor bipartite Ramsey numbers involving cycles and a small number of colors, The size of 3-uniform hypergraphs with given matching number and codegree, Degree powers in graphs with a forbidden forest, Erdős-Gallai stability theorem for linear forests, Edge-colorings of complete graphs that avoid polychromatic trees, A condition for a graph to contain \(k\)-matching., On the random version of the Erdős matching conjecture, Spectral extremal results with forbidding linear forests, The spectral radius of graphs without long cycles, Minimizing the number of edges in \(\mathcal{C}_{\geq r} \)-saturated graphs, General lemmas for Berge-Turán hypergraph problems, A short derivation for Turán numbers of paths, The number of edges, spectral radius and Hamilton-connectedness of graphs, Covering a graph with cycles of length at least 4, Graphs with almost all edges in long cycles, Long cycles, heavy cycles and cycle decompositions in digraphs, The structure of hypergraphs without long Berge cycles, An Erdős-Gallai type theorem for vertex colored graphs, Maximizing the number of cliques in graphs with given matching number, Properly colored \(C_4\)'s in edge-colored graphs, On the anti-Ramsey numbers of linear forests, Spectral analogues of Erdős' theorem on Hamilton-connected graphs, The Turán number of star forests, Minimum degree and size conditions for the proper connection number of graphs, Some generalized bipartite Ramsey numbers involving short cycles, A variation of the Erdős-Sós conjecture in bipartite graphs, The extremal \(\alpha \)-index of graphs with no 4-cycle and 5-cycle, The Ramsey numbers for a triple of long cycles, Connected hypergraphs without long Berge-paths, Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs, Old and new applications of Katona's circle, Cycles of given lengths in hypergraphs, Note on long paths in Eulerian digraphs, Inverting the Turán problem with chromatic number, Generalized Turán number of even linear forests, On the Turán number of theta graphs, Star-critical Ramsey numbers of cycles versus wheels, On the maximal colorings of complete graphs without some small properly colored subgraphs, The Turán number of the square of a path, Tibor Gallai, Packing of graphs - a survey, Weakly pancyclic graphs, Hamiltonicity of 2-connected quasi-claw-free graphs, Maximum bipartite subgraphs in graphs without short cycles, Personal reminiscences and remarks on the mathematical work of Tibor Gallai, Planar Turán numbers on short cycles of consecutive lengths, Threshold Ramsey multiplicity for paths and even cycles, Tibor Gallai - seventy years old, Universal graphs with forbidden subgraphs and algebraic closure, On the size of the product of overlapping families, Star-critical Ramsey numbers of wheels versus odd cycles, Maximum size of a graph with given fractional matching number, Path Ramsey numbers in multicolorings, The structure of graphs with given lengths of cycles, The maximum number of stars in a graph without linear forest, Ramsey and Gallai-Ramsey numbers for the union of paths and stars, Further results on the generalized Turán number of spanning linear forests, Maxima of the \(Q\)-index: forbidden a Fan, Spaces of symmetric matrices of bounded rank, Inverse Turán numbers, The generalized Turán number of spanning linear forests, Extremal graphs for two vertex-disjoint copies of a clique, Dense on-line arbitrarily partitionable graphs, Saturation spectrum of paths and stars, On Hamiltonian bipartite graphs, On the structure of linear graphs, Minimal paths and cycles in set systems, Disjoint complete minors and bipartite minors, The \((p, q)\)-extremal problem and the fractional chromatic number of Kneser hypergraphs, The Turán number of disjoint copies of paths, Fractional and integer matchings in uniform hypergraphs, Singular Turán numbers and worm-colorings, The Turán number for \(4 \cdot S_{\ell}^1\), On small balanceable, strongly-balanceable and omnitonal graphs, On some extremal problems in graph theory, Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture, The extremal function for disconnected minors, Gallai-Ramsey numbers for rainbow \(P_5\) and monochromatic fans or wheels, The minimum vertex degree for an almost-spanning tight cycle in a 3-uniform hypergraph, Extremal graphs for blow-ups of keyrings, On Turán number for \(S_{\ell_1} \cup S_{\ell_2}\), Proper connection and size of graphs, On the anti-Ramsey number of forests, Disjoint directed cycles with specified lengths in directed bipartite graphs, The Erdős matching conjecture and concentration inequalities, Remarks on the Erdős matching conjecture for vector spaces, The signless Laplacian spectral radius of graphs with forbidding linear forests, Extremal graphs for edge blow-up of graphs, Extremal problems of Erdős, Faudree, Schelp and Simonovits on paths and cycles, Sufficient conditions for graphs to be spanning connected, Turán numbers of complete 3-uniform Berge-hypergraphs, An Erdős-Gallai-type theorem for keyrings, On the maximum number of edges in hypergraphs with fixed matching and clique number, The formula for Turán number of spanning linear forests, Disjoint directed cycles in directed graphs, On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees, The maximum spectral radius of graphs without spanning linear forests, Turán numbers of Berge trees, Forbidden rainbow subgraphs that force large monochromatic or multicolored \(k\)-connected subgraphs, Generalized Turán problems for even cycles, The multicolour size-Ramsey number of powers of paths, Unbalanced spanning subgraphs in edge labeled complete graphs, Hypergraph Turán numbers of linear cycles, Triangles in graphs without bipartite suspensions, The Ramsey numbers of wheels versus odd cycles, Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth, The Turán number of directed paths and oriented cycles, Binary matroids with no 4-spike minors, Disjoint long cycles in a graph, Exact Ramsey numbers of odd cycles via nonlinear optimisation, Revisit of Erdős-Gallai's theorem on the circumference of a graph, On the vertex \(k\)-path cover, A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture, Asymptotic density of graphs excluding disconnected minors, Structure of the largest subgraphs of \(G_{n , p}\) with a given matching number, An analogue of the Erdős-Gallai theorem for random graphs, On the size of shadow-added intersecting families, Tilings in graphons, Maximum cuts in \(\mathscr{H} \)-free graphs, The Erdős-Sós conjecture for spiders, The codiameter of a 2-connected graph, Cycles and stability, The maximum number of copies of \(K_{r,s}\) in graphs without long cycles or paths, The Turán number of \(k \cdot S_\ell \), The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture, Linear Turán numbers of acyclic triple systems, Some new results on the Turán number of star forests, Breaking the rhythm on graphs, Maxima of the \(Q\)-index: forbidden odd cycles, A spectral condition for odd cycles in graphs, Ramsey-goodness -- and otherwise, Maxima of the \(Q\)-index: forbidden even cycles, On mutually independent Hamiltonian paths, Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions, On the Turán number for the hexagon, Matching polytons, On extremal hypergraphs for forests of tight paths, On the maximum size of subfamilies of labeled set with given matching number, Linear trees in uniform hypergraphs, Edge-colorings of graphs avoiding fixed monochromatic subgraphs with linear Turán number, Cycles Avoiding a Color in Colorful Graphs, Strong cliques and forbidden cycles, \(\mathcal{F}\)-saturation games, Lagrangian densities of enlargements of matchings in hypergraphs, A domination algorithm for {0,1}-instances of the travelling salesman problem, Two results about the Turán number of star forests, The shifting method and generalized Turán number of matchings, On the potential function of an arbitrary graph \(H\), Generalized Ramsey numbers: forbidding paths with few colors, Families of finite sets satisfying intersection restrictions, On \(r\)-uniform hypergraphs with circumference less than \(r\), The Turań number of \(2P_7\), Avoiding long Berge cycles, Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman, Large cycles in graphs, Energy conditions for Hamiltonicity of graphs, Ramsey numbers for cycles in graphs, On the existence of triangulated spheres in 3-graphs, and related problems, Minimal colorings for properly colored subgraphs, On 2-connected hypergraphs with no long cycles, Signless Laplacian spectral conditions for Hamiltonicity of graphs, Multicolour Ramsey numbers of paths and even cycles, Ramsey numbers of large even cycles and fans, Counterexamples to Gerbner's conjecture on stability of maximal F‐free graphs, On the saturation spectrum of families of cycle subdivisions, On the \(A_\alpha\)-spectral radius of graphs without linear forests, Embedding bipartite distance graphs under Hamming metric in finite fields, The Ramsey number of a long even cycle versus a star, Localized versions of extremal problems, The maximum number of cliques in graphs with prescribed order, circumference and minimum degree, Turán‐type problems for long cycles in random and pseudo‐random graphs, Book free 3-uniform hypergraphs, Families with restricted matching number and multiply covered shadows, Non-Hamiltonian graphs with large minimum degree, The bipartite Turán number and spectral extremum for linear forests, Turán graphs with bounded matching number, Spectral Turán problems for intersecting even cycles, Graphs without a Rainbow Path of Length 3, On Turán problems with bounded matching number, Stability of extremal connected hypergraphs avoiding Berge-paths, Extremal numbers for disjoint copies of a clique, The complete value of the Turán number of \(3K_{p+1}\)
Cites Work
