Top

Journal of Applied and Industrial Mathematics

Published in:

01-09-2023

Hypergraph Edge Representations with the Use of Homological Paths

Published in: Journal of Applied and Industrial Mathematics | Issue 3/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the problem of realization of hypergraphs on a graph provided each hyperedge is realized by a subgraph in which exactly two vertices have odd degree. This problem is related to Cycle Double Cover conjecture. We prove that checking the existence of realization is computationally hard. The hardness is proved in various settings: for realizations on all graphs, on simple graphs, and on graphs from several restricted classes.

previous article On Trees with a Given Diameter and the Extremal Number of Distance- Independent Sets

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

The name is justified in that in the case of a planar graph and cycles that are the boundaries of the faces, the usual construction of a geometrically dual graph is obtained (see [1, Sec. 40, p. 169 ]).

V. A. Emelichev, O. I. Mel’nikov, V. I. Sarvanov, R. I. Tyshkevich, Lectures on Graph Theory (Nauka, Moscow, 1990) [in Russian].MATH

R. E. Tarjan and M. Yannakakis, “Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs,” SIAM J. Comput. 13 (3), 566–579 (1984).MathSciNetCrossRefMATH

K. Buchin, M. van Kreveld, H. Meijer, B. Speckmann, and K. Verbeek, “On planar supports for hypergraphs,” in Vol. 5849 of Lect. Notes Comput. Sci.: Graph Drawing. Rev. Pap. 17th Int. Symp. (Chicago, USA, September 22–25, 2009) (Springer, Heidelberg, 2010), 345–356.

U. Brandes, S. Cornelsen, B. Pampel, and A. Sallaberry, “Blocks of hypergraphs: Applied to hypergraphs and outerplanarity,” in Vol. 6460 of Lect. Notes Comput. Sci.: Comb. Algorithms. Rev. Sel. Pap. 21st Int. Workshop (London, UK, July 26–28, 2010) (Springer, Heidelberg, 2011), 201–211.

D. S. Johnson and H. O. Pollak, “Hypergraph planarity and the complexity of drawing Venn diagrams,” J. Graph Theory 11 (3), 309–325 (1987).MathSciNetCrossRefMATH

U. Brandes, S. Cornelsen, B. Pampel, and A. Sallaberry, “Path-based supports for hypergraphs,” in Vol. 6460 of Lect. Notes Comput. Sci.: Comb. Algorithms. Rev. Sel. Pap. 21st Int. Workshop (London, UK, July 26–28, 2010) (Springer, Heidelberg, 2011), 20–33.

G. Szekeres, “Polyhedral decompositions of cubic graphs,” Bull. Aust. Math. Soc. 8, 367–387 (1973).MathSciNetCrossRefMATH

P. D. Seymour, “Sums of circuits,” in Graph Theory and Related Topics (Academic Press, New York, 1979), 341–355.

C. Q. Zhang, Integer Flows and Cycle Covers of Graphs (Marcel Dekker, New York, 1997).

10.

R. Diestel, Graph Theory (Springer, Heidelberg–New York, 2000; Izd. Inst. Mat., Novosibirsk, 2002).MATH

11.

M. Tarsi, “Semi-duality and the cycle double cover conjecture,” J. Comb. Theory. Ser. B 41 (3), 332–340 (1986).MathSciNetCrossRefMATH

Title: Hypergraph Edge Representations with the Use of Homological Paths
Publication date: 01-09-2023
Published in: Journal of Applied and Industrial Mathematics / Issue 3/2023
Print ISSN: 1990-4789
Electronic ISSN: 1990-4797
DOI: https://doi.org/10.1134/S1990478923030201

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 3/2023

On Graphs and Structural Formulas of the Mechanisms Theory

On the Integrability and Stability of Stationary Solutions of the Goryachev–Sretensky Gyrostat

On Trees with a Given Diameter and the Extremal Number of Distance- Independent Sets

Additional Constraints for Dynamic Competitive Facility Location Problem

On the Equilibrium of Elastic Bodies with a Weakly Curved Junction

Exact Traveling Wave Solutions of One-Dimensional Models of Cancer Invasion

Premium Partners