Connectivity and other invariants of generalized products of graphs

DOI10.1007/S10474-015-0487-8zbMATH Open1363.05219arXiv1305.2729OpenAlexW2048654103MaRDI QIDQ313405FDOQ313405

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

Publication date: 9 September 2016

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

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.

Full work available at URL: https://arxiv.org/abs/1305.2729

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

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)

Cites Work

• Graph derivatives
• Title not available (Why is that?)
• The Kronecker Product of Graphs
• Title not available (Why is that?)
• Associative graph products and their independence, domination and coloring numbers
• n-tuple colorings and associated graphs
• The chromatic number and other functions of the lexicographic product
• On the domination number of cross products of graphs
• On a Vizing-like conjecture for direct product graphs
• Labeling constructions using digraph products
• Title not available (Why is that?)
• BI-MAGIC AND OTHER GENERALIZATIONS OF SUPER EDGE-MAGIC LABELINGS
• Vizing's conjecture: a survey and recent results
• Labeling generating matrices
• The power of digraph products applied to labelings
• Lower bounds for the domination number and the total domination number of direct product graphs
• Dominating direct products of graphs

Cited In (8)

• Domination parameters on Cayley digraphs of transformation semigroups with fixed sets
• Title not available (Why is that?)
• Connectedness and Ingram-Mahavier products
• Connectivity of the generalized hierarchical product of graphs
• The connectivity of generalized graph products
• Path connectivity of \(k\)-generalized projectors
• Group connectivity of semistrong product of graphs
• Title not available (Why is that?)

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)