Displaying similar documents to “Two new classes of trees embeddable into hypercubes”

The inertia of unicyclic graphs and bicyclic graphs

Ying Liu (2013)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

Let G be a graph with n vertices and ν(G) be the matching number of G. The inertia of a graph G, In(G) = (n₊,n₋,n₀) is an integer triple specifying the numbers of positive, negative and zero eigenvalues of the adjacency matrix A(G), respectively. Let η(G) = n₀ denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G) = n - 2ν(G). Guo et al. [Ji-Ming Guo, Weigen Yan and Yeong-Nan Yeh. On the nullity and the matching number...

On θ-graphs of partial cubes

Sandi Klavžar, Matjaz Kovse (2007)

Discussiones Mathematicae Graph Theory

Similarity:

The Θ-graph Θ(G) of a partial cube G is the intersection graph of the equivalence classes of the Djoković-Winkler relation. Θ-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, Θ(G) is complete if and only if G can be obtained from K₁ by a sequence of (newly introduced) dense expansions. Θ-graphs are also compared with familiar concepts of crossing graphs and τ-graphs.

Radio Graceful Hamming Graphs

Amanda Niedzialomski (2016)

Discussiones Mathematicae Graph Theory

Similarity:

For k ∈ ℤ+ and G a simple, connected graph, a k-radio labeling f : V (G) → ℤ+ of G requires all pairs of distinct vertices u and v to satisfy |f(u) − f(v)| ≥ k + 1 − d(u, v). We consider k-radio labelings of G when k = diam(G). In this setting, f is injective; if f is also surjective onto {1, 2, . . . , |V (G)|}, then f is a consecutive radio labeling. Graphs that can be labeled with such a labeling are called radio graceful. In this paper, we give two results on the existence of radio...

On dually compact closed classes of graphs and BFS-constructible graphs

Norbert Polat (2003)

Discussiones Mathematicae Graph Theory

Similarity:

A class C of graphs is said to be dually compact closed if, for every infinite G ∈ C, each finite subgraph of G is contained in a finite induced subgraph of G which belongs to C. The class of trees and more generally the one of chordal graphs are dually compact closed. One of the main part of this paper is to settle a question of Hahn, Sands, Sauer and Woodrow by showing that the class of bridged graphs is dually compact closed. To prove this result we use the concept of constructible...

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.

Arboreal structure and regular graphs of median-like classes

Bostjan Brešar (2003)

Discussiones Mathematicae Graph Theory

Similarity:

We consider classes of graphs that enjoy the following properties: they are closed for gated subgraphs, gated amalgamation and Cartesian products, and for any gated subgraph the inverse of the gate function maps vertices to gated subsets. We prove that any graph of such a class contains a peripheral subgraph which is a Cartesian product of two graphs: a gated subgraph of the graph and a prime graph minus a vertex. Therefore, these graphs admit a peripheral elimination procedure which...

Characterizing Cartesian fixers and multipliers

Stephen Benecke, Christina M. Mynhardt (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let G ☐ H denote the Cartesian product of the graphs G and H. In 2004, Hartnell and Rall [On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24(3) (2004), 389-402] characterized prism fixers, i.e., graphs G for which γ(G ☐ K₂) = γ(G), and noted that γ(G ☐ Kₙ) ≥ min{|V(G)|, γ(G)+n-2}. We call a graph G a consistent fixer if γ(G ☐ Kₙ) = γ(G)+n-2 for each n such that 2 ≤ n < |V(G)|- γ(G)+2, and characterize this class of graphs. Also...