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!
cited_by cdi_FETCH-LOGICAL-c227t-c535d690d0ce2e563fac2c6aa96910123bbff126aaf967a31d598f10f0fc3cac3
cites cdi_FETCH-LOGICAL-c227t-c535d690d0ce2e563fac2c6aa96910123bbff126aaf967a31d598f10f0fc3cac3
container_end_page
container_issue
container_start_page 103479
container_title European journal of combinatorics
container_volume 102
creator Cavaleri, Matteo
D’Angeli, Daniele
Donno, Alfredo
description 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.
doi_str_mv 10.1016/j.ejc.2021.103479
format article
fullrecord <record><control><sourceid>elsevier_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1016_j_ejc_2021_103479</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0195669821001736</els_id><sourcerecordid>S0195669821001736</sourcerecordid><originalsourceid>FETCH-LOGICAL-c227t-c535d690d0ce2e563fac2c6aa96910123bbff126aaf967a31d598f10f0fc3cac3</originalsourceid><addsrcrecordid>eNp9j81OwzAQhC0EEqHwANz8Aglemzg1nFDFn1SJC5yt7dpuHZWksiMkeHpchTOn3ZnVrOZj7BpEAwL0Td_4nhopJBStbjtzwioQpq2N6eCUVQLKrrVZnrOLnHshAFqlKna32mFCmnyKPzjFcch8DHwfB8-3CQ-7zOPAc9wO3nEcHN9i0fPlkp0F3Gd_9TcX7OPp8X31Uq_fnl9XD-uapOymmlrVOm2EE-Slb7UKSJI0otGmVJdqswkBZDGC0R0qcK1ZBhBBBFKEpBYM5r-UxpyTD_aQ4iembwvCHuFtbwu8PcLbGb5k7ueML8W-ok82U_QDeReTp8m6Mf6T_gWAbWIU</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Characterizations of line graphs in signed and gain graphs</title><source>ScienceDirect Freedom Collection</source><creator>Cavaleri, Matteo ; D’Angeli, Daniele ; Donno, Alfredo</creator><creatorcontrib>Cavaleri, Matteo ; D’Angeli, Daniele ; Donno, Alfredo</creatorcontrib><description>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.</description><identifier>ISSN: 0195-6698</identifier><identifier>EISSN: 1095-9971</identifier><identifier>DOI: 10.1016/j.ejc.2021.103479</identifier><language>eng</language><publisher>Elsevier Ltd</publisher><ispartof>European journal of combinatorics, 2022-05, Vol.102, p.103479, Article 103479</ispartof><rights>2021 Elsevier Ltd</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c227t-c535d690d0ce2e563fac2c6aa96910123bbff126aaf967a31d598f10f0fc3cac3</citedby><cites>FETCH-LOGICAL-c227t-c535d690d0ce2e563fac2c6aa96910123bbff126aaf967a31d598f10f0fc3cac3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Cavaleri, Matteo</creatorcontrib><creatorcontrib>D’Angeli, Daniele</creatorcontrib><creatorcontrib>Donno, Alfredo</creatorcontrib><title>Characterizations of line graphs in signed and gain graphs</title><title>European journal of combinatorics</title><description>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.</description><issn>0195-6698</issn><issn>1095-9971</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><recordid>eNp9j81OwzAQhC0EEqHwANz8Aglemzg1nFDFn1SJC5yt7dpuHZWksiMkeHpchTOn3ZnVrOZj7BpEAwL0Td_4nhopJBStbjtzwioQpq2N6eCUVQLKrrVZnrOLnHshAFqlKna32mFCmnyKPzjFcch8DHwfB8-3CQ-7zOPAc9wO3nEcHN9i0fPlkp0F3Gd_9TcX7OPp8X31Uq_fnl9XD-uapOymmlrVOm2EE-Slb7UKSJI0otGmVJdqswkBZDGC0R0qcK1ZBhBBBFKEpBYM5r-UxpyTD_aQ4iembwvCHuFtbwu8PcLbGb5k7ueML8W-ok82U_QDeReTp8m6Mf6T_gWAbWIU</recordid><startdate>202205</startdate><enddate>202205</enddate><creator>Cavaleri, Matteo</creator><creator>D’Angeli, Daniele</creator><creator>Donno, Alfredo</creator><general>Elsevier Ltd</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>202205</creationdate><title>Characterizations of line graphs in signed and gain graphs</title><author>Cavaleri, Matteo ; D’Angeli, Daniele ; Donno, Alfredo</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c227t-c535d690d0ce2e563fac2c6aa96910123bbff126aaf967a31d598f10f0fc3cac3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Cavaleri, Matteo</creatorcontrib><creatorcontrib>D’Angeli, Daniele</creatorcontrib><creatorcontrib>Donno, Alfredo</creatorcontrib><collection>CrossRef</collection><jtitle>European journal of combinatorics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Cavaleri, Matteo</au><au>D’Angeli, Daniele</au><au>Donno, Alfredo</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Characterizations of line graphs in signed and gain graphs</atitle><jtitle>European journal of combinatorics</jtitle><date>2022-05</date><risdate>2022</risdate><volume>102</volume><spage>103479</spage><pages>103479-</pages><artnum>103479</artnum><issn>0195-6698</issn><eissn>1095-9971</eissn><abstract>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.</abstract><pub>Elsevier Ltd</pub><doi>10.1016/j.ejc.2021.103479</doi></addata></record>
fulltext fulltext
identifier ISSN: 0195-6698
ispartof European journal of combinatorics, 2022-05, Vol.102, p.103479, Article 103479
issn 0195-6698
1095-9971
language eng
recordid cdi_crossref_primary_10_1016_j_ejc_2021_103479
source ScienceDirect Freedom Collection
title Characterizations of line graphs in signed and gain graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-26T15%3A51%3A13IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-elsevier_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Characterizations%20of%20line%20graphs%20in%20signed%20and%20gain%20graphs&rft.jtitle=European%20journal%20of%20combinatorics&rft.au=Cavaleri,%20Matteo&rft.date=2022-05&rft.volume=102&rft.spage=103479&rft.pages=103479-&rft.artnum=103479&rft.issn=0195-6698&rft.eissn=1095-9971&rft_id=info:doi/10.1016/j.ejc.2021.103479&rft_dat=%3Celsevier_cross%3ES0195669821001736%3C/elsevier_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c227t-c535d690d0ce2e563fac2c6aa96910123bbff126aaf967a31d598f10f0fc3cac3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true