Characterizations of line graphs in signed and gain graphs

We generalize three classical characterizations of line graphs to line graphs of signed and gain graphs: the Krausz’s characterization, the van Rooij and Wilf’s characterization and the Beineke’s characterization. In particular, we present a list of forbidden gain subgraphs characterizing the class...

Full description

Saved in:
Bibliographic Details
Published in:European journal of combinatorics 2022-05, Vol.102, p.103479, Article 103479
Main Authors: Cavaleri, Matteo, D’Angeli, Daniele, Donno, Alfredo
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We generalize three classical characterizations of line graphs to line graphs of signed and gain graphs: the Krausz’s characterization, the van Rooij and Wilf’s characterization and the Beineke’s characterization. In particular, we present a list of forbidden gain subgraphs characterizing the class of gain-line graphs. In the case of a signed graph whose underlying graph is a line graph, this list consists of exactly four signed graphs. Under the same hypothesis, we prove that a signed graph is the line graph of a signed graph if and only if its eigenvalues are either greater than −2, or less than 2, depending on which particular definition of line graph is adopted.
ISSN:0195-6698
1095-9971
DOI:10.1016/j.ejc.2021.103479