Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao zbMATH Openarrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2023
Data sources: zbMATH Open
SIAM Journal on Discrete Mathematics
Article . 2023 . Peer-reviewed
Data sources: Crossref
DBLP
Article
Data sources: DBLP
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Packing Signatures in Signed Graphs

Packing signatures in signed graphs
Authors: Reza Naserasr; Weiqiang Yu;

Packing Signatures in Signed Graphs

Abstract

A signed graph \((G,\sigma)\) is a graph \(G\) equipped with a signature \(\sigma\), which assigns to each edge of \(G\) a sign (either \(+\) or \(-\) ). A switching at a vertex \(v\) is the product of the sign of the edges incident at \(v\) with \(-1\). The key concept that distinguishes a signed graph from a \(2\)-edge-colored graph is the notion of switching. The paper introduces the concept of the signature packing number, denoted as \(\rho(G,\sigma)\) for a signed graph \((G,\sigma)\). The authors define this notion and establish a significant result regarding its properties. They prove that for any signed graph \((G,\sigma)\), the packing number \(\rho(G,\sigma)\) is greater than or equal to \(d + 1\) if and only if the signed graph is homomorphic to \(S\mathcal{P}\mathcal{C}_{d}^{o}\), where \(S\mathcal{P}\mathcal{C}_{d}^{o}\) is obtained from \(S\mathcal{P}\mathcal{C}_{d}\) (signed projective cube of dimension \(d\)) by adding a positive loop to every vertex. Additionally, the authors demonstrate that the packing number \(\rho(G,\sigma)\) is bounded above by the length of the shortest all-negative closed walk, denoted as \(g_{-}(G,\sigma)\). Particularly, they show that equality in this bound is achieved when considering the signed graph \((K_{4},-)\). The main finding of the research is that the packing number of a signed graph is consistently odd, except in the case of bipartite graphs. Furthermore, the authors establish a stronger version of the well-known result ``A simple graph \(G\) is \(4\)-colorable if and only if \(\rho(G,\sigma)\geq 2\)'' within the realm of signed graphs. They present the result: ``If \(G\) is a \(K_5\)-minor-free bipartite simple graph, then for any signature \(\sigma,\) packing number is greater than equal to \(4\)''. This result appears to surpass the implications of the classical \(4\)-color theorem. Moreover, the paper discusses the practical implications of the packing number result, especially in smaller graph classes where \(4\)-coloring can be verified without relying on the \(4\)-color theorem. In such cases, the result regarding the packing number becomes independent of the \(4\)-color theorem, enhancing its applicability and usefulness.

Keywords

signed graph, packing number, signed projective cubes, homomorphisms, Signed and weighted graphs, Planar graphs; geometric and topological aspects of graph theory

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    3
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
3
Top 10%
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!