Show simple item record

dc.contributor.authorLópez Masip, Susana-Clara
dc.contributor.authorMuntaner Batle, F. A.
dc.date.accessioned2019-06-10T11:18:30Z
dc.date.available2019-06-10T11:18:30Z
dc.date.issued2015
dc.identifier.issn0236-5294
dc.identifier.urihttp://hdl.handle.net/10459.1/66433
dc.description.abstractFigueroa-Centeno et al. [4] introduced the following product of digraphs let D be a digraph and let Γ be a family of digraphs such that V (F) = V for every F∈Γ . Consider any function h:E(D)→Γ . Then the product D⊗hΓ is the digraph with vertex set V(D)×V and ((a,x),(b,y))∈E(D⊗hΓ) if and only if (a,b)∈E(D) and (x,y)∈E(h(a,b)) . In this paper, we deal with the undirected version of the ⊗h -product, which is a generalization of the classical direct product of graphs and, motivated by the ⊗h -product, we also recover a generalization of the classical lexicographic product of graphs, namely the ∘h -product, that was introduced by Sabidussi in 1961. We provide two characterizations for the connectivity of G⊗hΓ that generalize the existing one for the direct product. For G∘hΓ , we provide exact formulas for the connectivity and the edge-connectivity, under the assumption that V (F) = V , for all F∈Γ . We also introduce some miscellaneous results about other invariants in terms of the factors of both, the ⊗h -product and the ∘h -product. Some of them are easily obtained from the corresponding product of two graphs, but many others generalize the existing ones for the direct and the lexicographic product, respectively. We end up the paper by presenting some structural properties. An interesting result in this direction is a characterization for the existence of a nontrivial decomposition of a given graph G in terms of ⊗h -product.
dc.description.sponsorshipThe research conducted in this document by the first author has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
dc.format.mimetypeapplication/pdf
dc.language.isoeng
dc.publisherSpringer
dc.relationMICINN/PN2008-2011/MTM2011-28800-C02-01
dc.relation.isformatofVersió postprint del document publicat a https://doi.org/10.1007/s10474-015-0487-8
dc.relation.ispartofActa Mathematica Hungarica, 2015, vol. 145, num. 2, p. 283-303
dc.rights(c) Springer, 2015
dc.rights(c) Akadémiai Kiadó, Budapest, 2015
dc.subject.classificationTeoria de grafs
dc.subject.otherGraph theory
dc.titleConnectivity and other invariants of generalized products of graphs
dc.typeinfo:eu-repo/semantics/article
dc.date.updated2019-06-10T11:18:31Z
dc.identifier.idgrec028499
dc.type.versioninfo:eu-repo/semantics/acceptedVersion
dc.rights.accessRightsinfo:eu-repo/semantics/openAccess
dc.identifier.doihttps://doi.org/10.1007/s10474-015-0487-8


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record