×

zbMATH — the first resource for mathematics

On maximal paths and circuits of graphs. (English) Zbl 0090.39401
Alle hier vorkommenden Graphen \(G\) haben \(n\) Knotenpunkte, \(\nu (G)\) sei die Kantenzahl von \(G\). \(C_k\) sei der vollständige Graph mit \(k\) Punkten. Ist der Graph jedes Punktes \(\geq {1 \over 2} (n-1)\) \((n\geq 4)\), dann gibt es in \(G\) einen hamiltonschen Kreis und zwei beliebige Punkte aus \(G\) können durch eine offene hamiltonsche Linie verbunden werden. — Ist \(\nu(G) < {1\over 2} nl\). bzw. \(>{1\over 2} (n-1)l\), so enthält \(G\) einen Weg, bzw. Kreis mit mehr als \(l\) Kanten. Die Schranke ist genau im Fall \(n=q(l+1)\), bzw. \(n=q(l-1)+1\), wie das Beispiel des Graphen zeigt, der Vereinigung von \(q\) Graphen \(C_{l+1}\) ist, bzw. des zusammengesetzten Graphen, der \(q\) Glieder hat, von denen jedes ein \(C_l\) ist. — Ist \(n\geq ({1\over 2}k+1)^3\) \((k\geq 1)\), \(\nu(G) > nk-{k+1 \choose 2} = \varphi(n,k)\), so enthält \(G\) einen Weg oder Kreis mit mehr als 2\(k\) Kanten. Daß die Schranke für \(\nu(G)\) genau ist, zeigt der Graph \(G^*_k\) (\(2k\leq n\)), der zusammengesetzt ist aus einem \(C_k\), einer aus \(n-k\) Punkten bestehenden Punktmenge \(Q\) und allen Kanten, die Punkte aus \(Q\) mit Punkten aus \(C_k\) verbinden. — Kanten heißen unabhängig, wenn sie paarweise keinen Punkt gemein haben. Ist \(k\) die Höchstzahl unabhängiger Kanten in \(G\), so ist \(\nu(G) \leq \max \left(\binom{2k+1}{2},\varphi(n,k)\right)\). Das Gleichheitszeichen ist nur möglich, wenn \(G=G^*_k\) oder \(G=C_{2k+1} \cup \{p_i\}\), wobei \(p_i\) isolierte Punkte sind.
Reviewer: H.Künneth

MSC:
05C35 Extremal problems in graph theory
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
Keywords:
topology
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] H. B. Belck, Reguläre Faktoren von Graphen,Journal f. reine u. angew. Math.,188 (1950), pp. 228–252. · Zbl 0040.26001
[2] C. Berge,Theorie des graphes et ses applications (Paris, 1958). · Zbl 0088.15404
[3] G. A. Dirac, Some theorems on abstract graphs,Proc. London Math. Soc. (3),2 (1952), pp. 69–81. · Zbl 0047.17001 · doi:10.1112/plms/s3-2.1.69
[4] P. Erdos andA. H. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc.,52 (1946), pp. 1087–1091. · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7
[5] T. Gallai, On factorisation of graphs,Acta Math. Acad. Sci. Hung.,1 (1950), pp. 133–153. · Zbl 0040.25901 · doi:10.1007/BF02022560
[6] D. König,Theorie der endlichen und unendlichen Graphen (Leipzig, 1936). · JFM 62.0654.05
[7] T. Kovári, Vera T. Sós andP. Turán, On a problem of K. Zarankiewicz,Colloquium Math.,3 (1954), pp. 50–57.
[8] D. J. Newman, A problem in graph theory,Amer. Math. Monthly,65 (1958), p. 611. · Zbl 0082.37903 · doi:10.2307/2309119
[9] P. Turán, Egy gráfelméleti szélsoértékfeladatról,Mat. és Fiz. Lapok,48 (1941), pp. 436–452.
[10] P. Turán, On the theory of graphs,Colloquium Math.,3 (1954), pp. 19–30. · Zbl 0055.17004
[11] K. Zarankiewicz, Sur les relations symétriques dans l’ensemble fini,Colloquium Math.,1 (1947), pp. 10–14. · Zbl 0038.19804
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.