×

Randomly H graphs. (English) Zbl 0655.05052

Let G be a graph containing a subgraph H without isolated vertices. The graph G is defined to be a randomly H graph if whenever F is a subgraph of G without isolated vertices that is isomorphic to a subgraph of H, then F can be extended to a subgraph \(H_ 1\) of G such that \(H_ 1\) is isomorphic to H.
The authors provide a historic background of the concept of how the word “randomly” is used in some areas of graph theory and use it to introduce the idea of randomly H graphs.
The authors characterize graphs that are randomly H graphs when H is \(2K_ 2\), \(P_ 3\), \(K_ n\), or \(C_ n\). They also characterize graphs G that are randomly H graphs for every subgraph H of G. These graphs are nK(1,m) (n,m\(\geq 1)\), \(nK_ 3(n\geq 1)\), \(K_ p(p\geq 4)\), \(C_ 4\), \(C_ 5\), and K(3,3).

MSC:

05C75 Structural characterization of families of graphs
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] BÄBLER F.: Über eine spezielle Klasse Eulerscher Graphen. Comment. Math. Helv. 27, 1953, 81-100. · Zbl 0050.17905
[2] BEHZAD M., CHARTRAND G., LESNIAK-FOSTER L.: Graphs V Digraphs. Wadsworth International, Belmont, CA, 1979. · Zbl 0403.05027
[3] CHARTRAND G., HKRONK H. V.: Randomly traceable graphs. SIAM J. Appl. Math. 16, 1968, 696-700. · Zbl 0164.54202
[4] CHARTRAND G., KRONK H. V., LICK D. R.: Randomly hamiltonian digraphs. Fund. Math. 65, 1969, 223-226. · Zbl 0181.27304
[5] CHARTRAND G., LICK D. R.: Randomly eulerian digraphs. Czech. Math. J. 21, 1971, 424-430. · Zbl 0221.05066
[6] CHARTRAND G., WHITE A. T.: Randomly traversable graphs. Elem. Math. 25, 1970, 101-107. · Zbl 0199.27401
[7] DIRAC G. A., THOMASSEN C.: Graphs in which every finite path is contained in a circuit. Math. Ann. 203, 1973, 65-75. · Zbl 0239.05129
[8] ERICKSON D. B.: Arbitrarily traceable graphs and digraphs. J. Combinatorial Theory Ser. B 19, 1975, 5-23. · Zbl 0278.05109
[9] FINK J. F.: Randomly antitraceable digraphs. J. Graph Theory 6, 1982, 481-488. · Zbl 0498.05036
[10] FINK J. F.: Randomly near-tranceable graphs.
[11] HARARY F.: On arbitrarily traceable graphs and directed graphs. Scripta Math. 23, 1957, 37-41. · Zbl 0084.19403
[12] HARARY F.: Graph Theory. Addison-Wesley, Reading, MA, 1969. · Zbl 0196.27202
[13] ORE O.: A problem regarding the tracing of graphs. Elem. Math. 6, 1951, 49-53. · Zbl 0043.38503
[14] PARSONS T. D.: Paths extendable to cycle. J. Graph Theory 2, 1978, 337-339. · Zbl 0419.05033
[15] SUMNER D. P.: Randomly matchable graphs. J. Graph Theory 3, 1979, 183-186. · Zbl 0404.05053
[16] THOMASSEN C.: On randomly Hamiltonian graphs. Math. Ann. 200, 1973, 195-208. · Zbl 0233.05121
[17] THOMASSEN C.: Graphs in which every path is contained in a Hamiltonian path. J. Reine Angew. Math. 268/269, 1974, 271-282. · Zbl 0273.05121
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.