Partial product of graphs and Vizing's conjecture

Ismael González Yero

Abstract


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 GSH = (V, E), where V = V1 × V2 and two vertices (ui, vj) and (uk, vl) are adjacent in GSH 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\boxtimesBH = (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, ukA, vj ∈ B, vl ∉ B$, ui ∼ uk and vj ∼ vl) or (uiA, uk ∈ A, vjB, 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.


Keywords


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

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.419.831

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications