Connectivity and other invariants of generalized products of graphs

DOI10.1007/S10474-015-0487-8MaRDI QIDQ313405zbMATH OpenOpenAlexFDO

Authors S. C. López, F. A. Muntaner-Batle

Publication date 9 September 2016

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.2729, http://hdl.handle.net/10459.1/66433

zbMATH Keywords

connectivitydirect productlexicographic product\(\otimes_h\)-product, \(\circ_h\)

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Figueroa-Centeno et al. introduced the following product of digraphs: let $D$ be a digraph and let $Gamma$ be a family of digraphs such that $V(F)=V$ for every $FinGamma$. Consider any function $h:E(D)longrightarrowGamma$. Then the product $Dotime{s}_{h}Gamma$ is the digraph with vertex set $V(D)imesV$ and $((a,x),(b,y))inE(Dotime{s}_{h}Gamma)$ if and only if $(a,b)inE(D)$ and $(x,y)inE(h(a,b))$. In this paper, we introduce the undirected version of the $otime{s}_h$-product, which is a generalization of the classical direct product of graphs and, motivated by it, we also recover a generalization of the classical lexicographic product of graphs that was introduced by Sabidussi en 1961. We study connectivity properties and other invariants in terms of the factors. We also present a new intersection graph that emerges when we characterize the connectivity of $otime{s}_h$-product of graphs.

Recommendations

• The generalized hierarchical product of graphs
• Independence number of generalized products of graphs
• Connectivity of lexicographic product and direct product of graphs.
• Connectivity of generalized Cartesian product graphs
• The generalized 3-connectivity of graph products

Cites work

• scientific article; zbMATH DE number 1998306 (Why is no real title available?)
• Associative graph products and their independence, domination and coloring numbers
• Bi-magic and other generalizations of super edge-magic labelings
• Connectivity of lexicographic product and direct product of graphs.
• Dominating direct products of graphs
• Graph derivatives
• Handbook of product graphs
• Labeling constructions using digraph products
• Labeling generating matrices
• Lower bounds for the domination number and the total domination number of direct product graphs
• On a Vizing-like conjecture for direct product graphs
• On the domination number of cross products of graphs
• The Kronecker Product of Graphs
• The chromatic number and other functions of the lexicographic product
• The power of digraph products applied to labelings
• Vizing's conjecture: a survey and recent results
• n-tuple colorings and associated graphs

Cited in

(11)

• Domination parameters on Cayley digraphs of transformation semigroups with fixed sets
• On the independence and domination numbers of replacement product graphs
• scientific article; zbMATH DE number 3985280 (Why is no real title available?)
• Connectedness and Ingram-Mahavier products
• The connectivity of generalized graph products
• Connectivity of the generalized hierarchical product of graphs
• Independence number of generalized products of graphs
• Path connectivity of \(k\)-generalized projectors
• Group connectivity of semistrong product of graphs
• scientific article; zbMATH DE number 1876957 (Why is no real title available?)
• Partially composed property of generalized lexicographic product graphs

This page was built for publication: Connectivity and other invariants of generalized products of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313405)