On domination numbers of graphs bundles
type: Item
instance of: scholarly article
title: On domination numbers of graphs bundles
zbMATH Open document ID: 1110.05079
DOI: 10.1007/BF02896459
author: Blaž Zmazek
author: Janez Žerovnik
published in: Journal of Applied Mathematics and Computing
publication date: 2006-12-04T00:00:00Z
review text: The Cartesian product \(G\square H\) of two graphs \(G\) and \(H\) is the graph with vertex set \(V_G\times V_H\) and \((a,c)(b,d)\) is an edge of \(G\square H\) if \(c=d\) and \(ab\in E_G\), or \(a=b\) and \(cd\in E_H\). Given two graphs \(B\) and \(F\), a graph \(G\) is Cartesian graph bundle with fibre \(F\) over the base graph \(B\) if there is a graph map \(p:G\rightarrow B\) such that for each vertex \(v\in V_B\), \(p^{-1}(v)\simeq F\), and for each edge \(e\in E_B\), \(p^{-1}(e)\simeq K_2\square F\). The bundle \(G\) is obviously determined by \(F, B\) and a mapping \(\varphi:B_E\rightarrow\text{Aut}(F)\) which assigns an automorphism of the graph \(F\) to any edge of \(B\), and is written \(G=B\square_\varphi F\). The authors study the domination number of graph bundles, in particular of the Cartesian graph bundles over cycles. Here, the domination number \(\gamma(G)\) of \(G\) is the minimum cardinality of a set \(D\subseteq V_G\) such that every vertex outside \(D\) has a neighbor in \(D\). The authors show that for any integer \(k\geq 0\) there exists a graph \(G\) such that \(\gamma(G\square_\varphi C_4)=\gamma(G)\gamma(C_4)-2k\). This implies that the Vizing's conjecture (i.e., \(\gamma(G\square H)\geq\gamma(G)\gamma(H)\) for all graphs \(G\) and \(H\)) cannot be generalized to graph bundles. They also discuss the donination number of `strong' graph bundles.
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 5076933
MaRDI profile type: Publication
cites work: On Vizing's conjecture
cites work: The domination numbers of the 5 × n and 6 × n grid graphs
cites work: An inequality related to Vizing's conjecture
cites work: Unit disk graphs
cites work: Q3777474
cites work: Associative products of graphs
cites work: Recognizing Cartesian graph bundles
cites work: Q3680873
cites work: On the domination of the products of graphs II: Trees
cites work: Coloring graph bundles
cites work: The chromatic numbers of graph bundles over cycles
cites work: Dominating Cartesian products of cycles
cites work: Algebraic approach to fasciagraphs and rotagraphs
cites work: Isomorphism Classes of Graph Bundles
cites work: Caracteristics polynomials of some grap bundlesII
cites work: Q4862239
cites work: An algorithm forK-convex closure and an application
cites work: Characteristic polynomials of some weighted graph bundles and its application to links
cites work: Recognizing weighted directed cartesian graph bundles
cites work: On recognizing Cartesian graph bundles
cites work: Algorithm for recognizing Cartesian graph bundles
cites work: Unique square property and fundamental factorizations of graph bundles
cites work: Q4934361
description: scientific article; zbMATH DE number 5076933