On token signed graphs
Open Access
- 15 July 2025
- journal article
- research article
- Published by Springer Nature in Journal of Algebraic Combinatorics
- Vol. 62 (1) , 1-17
Abstract
We introduce the concept of a k-token signed graph and study some of its combinatorial and algebraic properties. We prove that two switching isomorphic signed graphs have switching isomorphic token graphs. Moreover, we show that the Laplacian spectrum of a balanced signed graph is contained in the Laplacian spectra of its k-token signed graph. Besides, we introduce and study the unbalance level of a signed graph, which is a new parameter that measures how far a signed graph is from being balanced. Moreover, we study the relation between the frustration index and the unbalance level of signed graphs and their token signed graphs.Keywords
All Related Versions
Funding Information
- Agència de Gestió d’Ajuts Universitaris i de Recerca (2021SGR00434, 2021SGR00434)
- Ministerio de Ciencia e Innovación (PID2020-115442RB-I00, PID2020-115442RB-I00)
- Universitat Politècnica de Catalunya (AGRUPS-2022, AGRUPS-2023)
- Universitat de Lleida
This publication has 13 references indexed in Scilit:
- Frustration-critical signed graphsDiscrete Applied Mathematics, 2022
- On the Laplacian spectra of token graphsLinear Algebra and its Applications, 2021
- Open problems in the spectral theory of signed graphsThe Art of Discrete and Applied Mathematics, 2018
- Frustration and isoperimetric inequalities for signed graphsDiscrete Applied Mathematics, 2017
- Balancedness and the least eigenvalue of Laplacian of signed graphsLinear Algebra and its Applications, 2014
- Six signed Petersen graphs, and their automorphismsDiscrete Mathematics, 2012
- Token GraphsGraphs and Combinatorics, 2011
- Symmetric squares of graphsJournal of Combinatorial Theory, Series B, 2007
- Signed graphsDiscrete Applied Mathematics, 1982
- On the notion of balance of a signed graph.The Michigan Mathematical Journal, 1953