Displaying similar documents to “Harary Index of Product Graphs”

Isomorphic components of direct products of bipartite graphs

Richard Hammack (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A standard result states the direct product of two connected bipartite graphs has exactly two components. Jha, Klavžar and Zmazek proved that if one of the factors admits an automorphism that interchanges partite sets, then the components are isomorphic. They conjectured the converse to be true. We prove the converse holds if the factors are square-free. Further, we present a matrix-theoretic conjecture that, if proved, would prove the general case of the converse; if refuted, it would...

Classification of tensor products of symmetric graphs

Wilfried Imrich, Aleš Pultr (1991)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In the category of symmetric graphs there are exactly five closed tensor products. If we omit the requirement of units, we obtain twelve more.

Oriented colouring of some graph products

N.R. Aravind, N. Narayanan, C.R. Subramanian (2011)

Discussiones Mathematicae Graph Theory

Similarity:

We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs.

A cancellation property for the direct product of graphs

Richard H. Hammack (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Given graphs A, B and C for which A×C ≅ B×C, it is not generally true that A ≅ B. However, it is known that A×C ≅ B×C implies A ≅ B provided that C is non-bipartite, or that there are homomorphisms from A and B to C. This note proves an additional cancellation property. We show that if B and C are bipartite, then A×C ≅ B×C implies A ≅ B if and only if no component of B admits an involution that interchanges its partite sets.

Associative graph products and their independence, domination and coloring numbers

Richard J. Nowakowski, Douglas F. Rall (1996)

Discussiones Mathematicae Graph Theory

Similarity:

Associative products are defined using a scheme of Imrich & Izbicki [18]. These include the Cartesian, categorical, strong and lexicographic products, as well as others. We examine which product ⊗ and parameter p pairs are multiplicative, that is, p(G⊗H) ≥ p(G)p(H) for all graphs G and H or p(G⊗H) ≤ p(G)p(H) for all graphs G and H. The parameters are related to independence, domination and irredundance. This includes Vizing's conjecture directly, and indirectly the Shannon capacity...

Interval edge colorings of some products of graphs

Petros A. Petrosyan (2011)

Discussiones Mathematicae Graph Theory

Similarity:

An edge coloring of a graph G with colors 1,2,...,t is called an interval t-coloring if for each i ∈ {1,2,...,t} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable, if there is an integer t ≥ 1 for which G has an interval t-coloring. Let ℜ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H ∈ 𝔑, then the Cartesian product...

The crossing numbers of certain Cartesian products

Marián Klešč (1995)

Discussiones Mathematicae Graph Theory

Similarity:

In this article we determine the crossing numbers of the Cartesian products of given three graphs on five vertices with paths.

C7-Decompositions of the Tensor Product of Complete Graphs

R.S. Manikandan, P. Paulraja (2017)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we consider a decomposition of Km × Kn, where × denotes the tensor product of graphs, into cycles of length seven. We prove that for m, n ≥ 3, cycles of length seven decompose the graph Km × Kn if and only if (1) either m or n is odd and (2) 14 | m(m − 1)n(n − 1). The results of this paper together with the results of [Cp-Decompositions of some regular graphs, Discrete Math. 306 (2006) 429–451] and [C5-Decompositions of the tensor product of complete graphs, Australasian...

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