Partial product of graphs and Vizing's conjecture

Ismael González Yero

Ars Mathematica Contemporanea, Tome 9 (2015) no. 1, pp. 19-25.

Résumé

Let G and H be two graphs with vertex sets V1 = {u1, . . . , un1} and V2 = {v1, . . . , vn2}, respectively. If S ⊂ V2, then the partial Cartesian product of G and H with respect to S is the graph G□SH = (V, E), where V = V1 × V2 and two vertices (ui, vj) and (uk, vl) are adjacent in G□SH if and only if either (ui = uk and vj ∼ vl) or (ui ∼ uk and vj = vl ∈ S). If A ⊂ V1 and B ⊂ V2, then the restricted partial strong product of G and H with respect to A and B is the graph GA\boxtimesB H = (V, E), where V = V1 × V2 and two vertices (ui, vj) and (uk, vl) are adjacent in GA\boxtimesBH if and only if either (ui = uk and vj ∼ vl) or (ui ∼ uk and vj = vl) or (ui ∈ A, uk ∉ A, vj ∈ B, vl ∉ B$, ui ∼ uk and vj ∼ vl) or (ui∉ A, uk ∈ A, vj∉ B, vl ∈ B, ui ∼ uk and vj ∼ vl). In this article we obtain Vizing-like results for the domination number and the independence domination number of the partial Cartesian product of graphs. Moreover we study the domination number of the restricted partial strong product of graphs.

Détail

DOI : 10.26493/1855-3974.419.831

Keywords: Domination, partial product graph, Cartesian product graph, strong product graph, Vizing's conjecture