Existence and nonexistence of universal graphs
Lawrence Moss (1989)
Fundamenta Mathematicae
Similarity:
Lawrence Moss (1989)
Fundamenta Mathematicae
Similarity:
Petrović, Miroslav (1991)
Publications de l'Institut Mathématique. Nouvelle Série
Similarity:
Vladislav Bína, Jiří Přibil (2015)
Commentationes Mathematicae Universitatis Carolinae
Similarity:
The paper brings explicit formula for enumeration of vertex-labeled split graphs with given number of vertices. The authors derive this formula combinatorially using an auxiliary assertion concerning number of split graphs with given clique number. In conclusion authors discuss enumeration of vertex-labeled bipartite graphs, i.e., a graphical class defined in a similar manner to the class of split graphs.
Peter Mihók, Jozef Miškuf, Gabriel Semanišin (2009)
Discussiones Mathematicae Graph Theory
Similarity:
A graph property is any isomorphism closed class of simple graphs. For a simple finite graph H, let → H denote the class of all simple countable graphs that admit homomorphisms to H, such classes of graphs are called hom-properties. Given a graph property 𝓟, a graph G ∈ 𝓟 is universal in 𝓟 if each member of 𝓟 is isomorphic to an induced subgraph of G. In particular, we consider universal graphs in → H and we give a new proof of the existence of a universal graph in → H, for any finite...
Izak Broere, Johannes Heidema, Peter Mihók (2013)
Discussiones Mathematicae Graph Theory
Similarity:
Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: For given m and n with m < n, m is adjacent to n if n has a 1 in the m’th position of its binary expansion. It is well known that R is a universal graph in the set [...] of all countable graphs (since every graph in [...] is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of [...] is provided....
Jaroslav Nešetřil (1978)
Mathematica Slovaca
Similarity:
I.B. Lackovic, D.M. Cvetkovic (1976)
Publications de l'Institut Mathématique [Elektronische Ressource]
Similarity:
Akiyama, Jin, Harary, Frank (1979)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Peter Hudák, Mária Maceková, Tomáš Madaras, Pavol Široczki (2016)
Discussiones Mathematicae Graph Theory
Similarity:
A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢). In this paper, we investigate light graphs in families of plane graphs of minimum degree 2 with prescribed girth and no adjacent 2-vertices, specifying several necessary conditions for their lightness and providing sharp bounds on φ and w...
Cvetkovic, Dragos M. (1983)
Publications de l'Institut Mathématique. Nouvelle Série
Similarity: