Efficient Direct Reconstruction of Bipartite (Multi)Graphs from Their Line Graphs Through a Characterization of Their Edges

Drago Bokal and Janja Jerebic ()
Additional contact information
Drago Bokal: Faculty of Natural Sciences and Mathematics, University of Maribor, 2000 Maribor, Slovenia
Janja Jerebic: Faculty of Organizational Sciences, University of Maribor, 4000 Kranj, Slovenia

Mathematics, 2025, vol. 13, issue 17, 1-17

Abstract: We study the line graphs of bipartite multigraphs, which naturally arise in combinatorics, game theory, and applications such as scheduling and motion planning. We introduce a new characterization of these graphs via valid partial assignments of the edges of the underlying bipartite multigraph to the vertices of its line graph. We show that an empty assignment extends to a complete one precisely when the graph is a line graph of a bipartite multigraph. Based on this, we design an O ( Δ ( G ) | E ( G ) | ) algorithm that incrementally constructs such assignments. The algorithm also provides a data structure supporting efficient solutions to problems of maximum clique, maximum weighted clique, minimum clique cover, chromatic number, and independence number. For line graphs of bipartite simple graphs these problems become solvable in linear time, improving on previously known polynomial-time results. For general bipartite multigraphs, our method enhances the O ( | V ( G ) | 3 ) recognition algorithm of Peterson and builds on the results of Demaine et al., Hedetniemi, Cook et al., and Gurvich and Temkin.

Keywords: UNO-graph; line graph; bipartite graph; bipartite multigraph; graph algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/17/2876/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/17/2876/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:17:p:2876-:d:1743382

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().