Displaying similar documents to “Prime Factorization And Domination In The Hierarchical Product Of Graphs”

A prime factor theorem for a generalized direct product

Wilfried Imrich, Peter F. Stadler (2006)

Discussiones Mathematicae Graph Theory

Similarity:

We introduce the concept of neighborhood systems as a generalization of directed, reflexive graphs and show that the prime factorization of neighborhood systems with respect to the the direct product is unique under the condition that they satisfy an appropriate notion of thinness.

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.

Factoring directed graphs with respect to the cardinal product in polynomial time II

Wilfried Imrich, Werner Klöckl (2010)

Discussiones Mathematicae Graph Theory

Similarity:

By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we...

Even [a,b]-factors in graphs

Mekkia Kouider, Preben Dahl Vestergaard (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let a and b be integers 4 ≤ a ≤ b. We give simple, sufficient conditions for graphs to contain an even [a,b]-factor. The conditions are on the order and on the minimum degree, or on the edge-connectivity of the graph.

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