Displaying similar documents to “On θ-graphs of partial cubes”

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

Isomorphic components of Kronecker product of bipartite graphs

Pranava K. Jha, Sandi Klavžar, Blaž Zmazek (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Weichsel (Proc. Amer. Math. Soc. 13 (1962) 47-52) proved that the Kronecker product of two connected bipartite graphs consists of two connected components. A condition on the factor graphs is presented which ensures that such components are isomorphic. It is demonstrated that several familiar and easily constructible graphs are amenable to that condition. A partial converse is proved for the above condition and it is conjectured that the converse is true in general.

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

Union of Distance Magic Graphs

Sylwia Cichacz, Mateusz Nikodem (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A distance magic labeling of a graph G = (V,E) with |V | = n is a bijection ℓ from V to the set {1, . . . , n} such that the weight w(x) = ∑y∈NG(x) ℓ(y) of every vertex x ∈ V is equal to the same element μ, called the magic constant. In this paper, we study unions of distance magic graphs as well as some properties of such graphs.

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

Graphs of low chordality.

Chandran, L.Sunil, Lozin, Vadim V., Subramanian, C.R. (2005)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

Similarity:

Dominating bipartite subgraphs in graphs

Gábor Bacsó, Danuta Michalak, Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.

The Thickness of Amalgamations and Cartesian Product of Graphs

Yan Yang, Yichao Chen (2017)

Discussiones Mathematicae Graph Theory

Similarity:

The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is a measurement of the closeness to the planarity of a graph, and it also has important applications to VLSI design, but it has been known for only few graphs. We obtain the thickness of vertex-amalgamation and bar-amalgamation of graphs, the lower and upper bounds for the thickness of edge-amalgamation and 2-vertex-amalgamation of graphs, respectively. We also study...

The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic

Yi Wang, Yi-Zheng Fan, Xiao-Xin Li, Fei-Fei Zhang (2015)

Discussiones Mathematicae Graph Theory

Similarity:

A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and...