The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Countable splitting graphs”

Universality for and in Induced-Hereditary Graph Properties

Izak Broere, Johannes Heidema (2013)

Discussiones Mathematicae Graph Theory

Similarity:

The well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal graphs in I with prescribed attributes. Then we contrast universality for and universality in induced-hereditary properties of graphs and show that the overwhelming majority of induced-hereditary...

The periphery graph of a median graph

Boštjan Brešar, Manoj Changat, Ajitha R. Subhamathi, Aleksandra Tepeh (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The periphery graph of a median graph is the intersection graph of its peripheral subgraphs. We show that every graph without a universal vertex can be realized as the periphery graph of a median graph. We characterize those median graphs whose periphery graph is the join of two graphs and show that they are precisely Cartesian products of median graphs. Path-like median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are...

Stable graphs

Klaus-Peter Podewski, Martin Ziegler (1978)

Fundamenta Mathematicae

Similarity:

The Existence Of P≥3-Factor Covered Graphs

Sizhong Zhou, Jiancheng Wu, Tao Zhang (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A spanning subgraph F of a graph G is called a P≥3-factor of G if every component of F is a path of order at least 3. A graph G is called a P≥3-factor covered graph if G has a P≥3-factor including e for any e ∈ E(G). In this paper, we obtain three sufficient conditions for graphs to be P≥3-factor covered graphs. Furthermore, it is shown that the results are sharp.

Characterizations of the Family of All Generalized Line Graphs-Finite and Infinite-and Classification of the Family of All Graphs Whose Least Eigenvalues ≥ −2

Gurusamy Rengasamy Vijayakumar (2013)

Discussiones Mathematicae Graph Theory

Similarity:

The infimum of the least eigenvalues of all finite induced subgraphs of an infinite graph is defined to be its least eigenvalue. In [P.J. Cameron, J.M. Goethals, J.J. Seidel and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976) 305-327], the class of all finite graphs whose least eigenvalues ≥ −2 has been classified: (1) If a (finite) graph is connected and its least eigenvalue is at least −2, then either it is a generalized line graph or it is represented...

Hereditarnia

Izak Broere, Peter Mihók (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Universality in Graph Properties with Degree Restrictions

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....

α-Labelings of a Class of Generalized Petersen Graphs

Anna Benini, Anita Pasotti (2015)

Discussiones Mathematicae Graph Theory

Similarity:

An α-labeling of a bipartite graph Γ of size e is an injective function f : V (Γ) → {0, 1, 2, . . . , e} such that {|ƒ(x) − ƒ(y)| : [x, y] ∈ E(Γ)} = {1, 2, . . . , e} and with the property that its maximum value on one of the two bipartite sets does not reach its minimum on the other one. We prove that the generalized Petersen graph PSn,3 admits an α-labeling for any integer n ≥ 1 confirming that the conjecture posed by Vietri in [10] is true. In such a way we obtain an infinite class...

Note on enumeration of labeled split graphs

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.

Regularity and Planarity of Token Graphs

Walter Carballosa, Ruy Fabila-Monroy, Jesús Leaños, Luis Manuel Rivera (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V, E) be a graph of order n and let 1 ≤ k < n be an integer. The k-token graph of G is the graph whose vertices are all the k-subsets of V, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper we characterize precisely, for each value of k, which graphs have a regular k-token graph and which connected graphs have a planar k-token graph.