Partial product of graphs and Vizing's conjecture

González Yero, Ismael

ARS MATHEMATICA CONTEMPORANEA, Tome 9 (2014), / Harvested from ARS MATHEMATICA CONTEMPORANEA

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

Publié le : 2014-01-01
DOI : https://doi.org/10.26493/1855-3974.419.831