Displaying similar documents to “Connectivity and planarity of Cayley 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...

Integral Cayley Sum Graphs and Groups

Xuanlong Ma, Kaishun Wang (2016)

Discussiones Mathematicae Graph Theory

Similarity:

For any positive integer k, let Ak denote the set of finite abelian groups G such that for any subgroup H of G all Cayley sum graphs CayS(H, S) are integral if |S| = k. A finite abelian group G is called Cayley sum integral if for any subgroup H of G all Cayley sum graphs on H are integral. In this paper, the classes A2 and A3 are classified. As an application, we determine all finite Cayley sum integral groups.

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.

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.

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