Displaying similar documents to “The crossing numbers of certain Cartesian products”

The crossing numbers of products of a 5-vertex graph with paths and cycles

Marián Klešč (1999)

Discussiones Mathematicae Graph Theory

Similarity:

There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with "small" graphs. Let H be the 5-vertex graph defined from K₅ by removing three edges incident with a common vertex. In this paper, we extend the earlier results to the Cartesian products of H × Pₙ and H × Cₙ, showing that in the general case the corresponding crossing numbers are 3n-1, and 3n for even n or 3n+1 if n is odd.

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

Weak k-reconstruction of Cartesian products

Wilfried Imrich, Blaz Zmazek, Janez Zerovnik (2003)

Discussiones Mathematicae Graph Theory

Similarity:

By Ulam's conjecture every finite graph G can be reconstructed from its deck of vertex deleted subgraphs. The conjecture is still open, but many special cases have been settled. In particular, one can reconstruct Cartesian products. We consider the case of k-vertex deleted subgraphs of Cartesian products, and prove that one can decide whether a graph H is a k-vertex deleted subgraph of a Cartesian product G with at least k+1 prime factors on at least k+1 vertices each, and that H uniquely...

On the crossing numbers of G □ Cₙ for graphs G on six vertices

Emília Draženská, Marián Klešč (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. The crossing numbers of G☐Cₙ for some graphs G on five and six vertices and the cycle Cₙ are also given. In this paper, we extend these results by determining crossing numbers of Cartesian products G☐Cₙ for some connected graphs G of order six with six and seven edges. In addition, we collect known results concerning crossing numbers of G☐Cₙ for graphs G on six vertices. ...

On the Crossing Numbers of Cartesian Products of Wheels and Trees

Marián Klešč, Jana Petrillová, Matúš Valo (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Bokal developed an innovative method for finding the crossing numbers of Cartesian product of two arbitrarily large graphs. In this article, the crossing number of the join product of stars and cycles are given. Afterwards, using Bokal’s zip product operation, the crossing numbers of the Cartesian products of the wheel Wn and all trees T with maximum degree at most five are established.

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 note on (k,l)-kernels in B-products of graphs

Iwona Włoch (1996)

Discussiones Mathematicae Graph Theory

Similarity:

B-products of graphs and their generalizations were introduced in [4]. We determined the parameters k, l of (k,l)-kernels in generalized B-products of graphs. These results are generalizations of theorems from [2].

On the Crossing Numbers of Cartesian Products of Stars and Graphs of Order Six

Marián Klešč, Štefan Schrötter (2013)

Discussiones Mathematicae Graph Theory

Similarity:

The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. According to their special structure, the class of Cartesian products of two graphs is one of few graph classes for which some exact values of crossing numbers were obtained. The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. Moreover, except of six graphs, the crossing numbers of Cartesian products G⃞K1,n for...

Products Of Digraphs And Their Competition Graphs

Martin Sonntag, Hanns-Martin Teichert (2016)

Discussiones Mathematicae Graph Theory

Similarity:

If D = (V, A) is a digraph, its competition graph (with loops) CGl(D) has the vertex set V and {u, v} ⊆ V is an edge of CGl(D) if and only if there is a vertex w ∈ V such that (u, w), (v, w) ∈ A. In CGl(D), loops {v} are allowed only if v is the only predecessor of a certain vertex w ∈ V. For several products D1 ⚬ D2 of digraphs D1 and D2, we investigate the relations between the competition graphs of the factors D1, D2 and the competition graph of their product D1 ⚬ D2.