Skip to Main content Skip to Navigation
Journal articles

Classification of edge-critical underlying absolute planar cliques for signed graphs

Abstract : A simple signed graph (G,Σ) is a simple graph G having two different types of edges, positive edges and negative edges, where Σ denotes the set of negative edges of G. A closed walk of a signed graph is positive (resp., negative) if it has even (resp., odd) number of negative edges, taking repeated edges into account. A homomorphism (resp., colored homomorphism) of a simple signed graph to another simple signed graph is a vertex-mapping that preserves adjacencies and signs of closed walks (resp., signs of edges). A simple signed graph (G,Σ) is a signed absolute clique (resp., (0,2)-absolute clique) if any homomorphism (resp., colored homomorphism) of it is an injective function, in which case G is called an underlying signed absolute clique (resp., underlying (0,2)-absolute clique). Moreover, G is edge-critical if G - e is not an underlying signed absolute clique (resp., underlying (0,2)-absolute clique) for any edge e of G. In this article, we characterize all edge-critical outerplanar underlying (0,2)-absolute cliques and all edge-critical planar underlying signed absolute cliques. We also discuss the motivations and implications of obtaining these exhaustive lists.
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01919007
Contributor : Julien Bensmail <>
Submitted on : Thursday, April 9, 2020 - 9:22:38 AM
Last modification on : Tuesday, May 26, 2020 - 6:50:53 PM

File

BNRS_revision2_v1.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01919007, version 2

Collections

Citation

Julien Bensmail, Soumen Nandi, Mithun Roy, Sagnik Sen. Classification of edge-critical underlying absolute planar cliques for signed graphs. The Australasian Journal of Combinatorics, Combinatorial Mathematics Society of Australasia (Inc.), 2020, 77 (1), pp.117-135. ⟨hal-01919007v2⟩

Share

Metrics

Record views

38

Files downloads

28