| Title: | Efficient direct reconstruction of bipartite (multi)graphs from their line graphs through a characterization of their edges |
|---|
| Authors: | ID Bokal, Drago (Author)
ID Jerebic, Janja (Author) |
|---|
| Files: |  https://www.mdpi.com/2227-7390/13/17/2876
 mathematics-13-02876-v2_(1).pdf (348,95 KB)
MD5: 4BC37062C9C753C32A5AF1F4835D85C0
|
|---|
| Language: | English |
|---|
| Work type: | Scientific work |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FOV - Faculty of Organizational Sciences in Kranj
|
|---|
| 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 |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Submitted for review: | 17.07.2025 |
|---|
| Article acceptance date: | 03.09.2025 |
|---|
| Publication date: | 05.09.2025 |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | 17 str. |
|---|
| Numbering: | Vol. 13, iss. 17, [article no.] 2876 |
|---|
| PID: | 20.500.12556/DKUM-95222  |
|---|
| UDC: | 37.018.43:004:616-036.21 |
|---|
| ISSN on article: | 2227-7390 |
|---|
| COBISS.SI-ID: | 248174339 |
|---|
| DOI: | 10.3390/math13172876 |
|---|
| Publication date in DKUM: | 09.09.2025 |
|---|
| Views: | 186 |
|---|
| Downloads: | 7 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
