Reconstruction of hypergraphs from line graphs and degree sequences

Simple item page
dc.contributor.authorGodinho, Aloysius
dc.date.accessioned2025-08-03T12:54:51Z
dc.date.available2025-08-03T12:54:51Z
dc.date.issued2021
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/450
dc.language.isoen
dc.publisherarXiv:2104.14863v1
dc.titleReconstruction of hypergraphs from line graphs and degree sequences
dc.typeArticle
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Math-12-10-4.pdf
Size:
194.38 KB
Format:
Adobe Portable Document Format
Download
Collections
Department of Mathematics