The Relative Signed Clique Number of Planar Graphs is 8
2019
A simple signed graph \((G, \varSigma )\) is a simple graph with a \(+\)ve or a −ve sign assigned to each of its edges where \(\varSigma \) denotes the set of −ve edges. A cycle is unbalanced if it has an odd number of −ve edges. A vertex subset R of \((G, \varSigma )\) is a relative signed clique if each pair of non-adjacent vertices of R is part of an unbalanced 4-cycle. The relative signed clique number \(\omega _{rs}((G, \varSigma ))\) of \((G,\varSigma )\) is the maximum value of |R| where R is a relative signed clique of \((G,\varSigma )\). Given a family \(\mathcal {F}\) of signed graphs, the relative signed clique number is \(\omega _{rs}(\mathcal {F}) = \max \{\omega _{rs}((G,\varSigma ))|(G,\varSigma ) \in \mathcal {F}\}\). For the family \(\mathcal {P}_3\) of signed planar graphs, the problem of finding the value of \(\omega _{rs}(\mathcal {P}_3)\) is an open problem. In this article, we close it by proving \(\omega _{rs}(\mathcal {P}_3)=8\).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
10
References
0
Citations
NaN
KQI