Reconstruction of hypergraphs from line graphs and degree sequences

Simple item page
dc.contributor.authorGodinho, Aloysius
dc.date.accessioned2025-04-05T05:51:27Z
dc.date.available2025-04-05T05:51:27Z
dc.date.issued2020
dc.description.abstractIn this paper we consider the problem to reconstruct a k-uniform hypergraph from its line graph. In general this problem is hard. We solve this problem when the number of hyperedges containing any pair of vertices is bounded. Given an integer sequence, constructing a k-uniform hypergraph with that as its degree sequence is NP-complete. Here we show that for constant integer sequences the question can be answered in polynomial time using Baranyai’s theorem.
dc.identifier.urihttp://rcca.ndl.gov.in/handle/123456789/155
dc.titleReconstruction of hypergraphs from line graphs and degree sequences
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
10-4.pdf
Size:
194.38 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
2020-2021