Structural and Parametric properties of Graphs Admitting Extremal 3-Uniform Linear Hypergraph Set-Indexers

Viji Paul; Beena Koshy

doi:10.26713/jims.v18i3.3799

Authors

Viji Paul Department of Mathematics, WMO Arts and Science College (affiliated to University of Calicut), Muttil 673122, Keralam, India https://orcid.org/0009-0002-2985-2875
Beena Koshy Department of Mathematics, Catholicate College (affiliated to Mahatma Gandhi University, Kottayam), Pathanamthitta 689645, Keralam, India https://orcid.org/0009-0008-7221-9622

DOI:

https://doi.org/10.26713/jims.v18i3.3799

Keywords:

Linear Hypergraph Set-Indexer, Cyclomatic number, Cyclicity, Conformality, Helly property, Duality

Abstract

A linear hypergraph set-indexer (LHSI) of a graph \(G\) is an injective set-valuation \(f: V(G)\rightarrow 2^X\) such that the associated vertex hypergraph \(H_f(G) = (X, f(V))\) and induced edge hypergraph \(H_{f^{\oplus}}(G) = (X, f^{\oplus}(E))\) are both linear. This paper investigates the structural and parametric relationships between \(G\) and these hypergraphs in the extremal case where the ground set \(X\) reaches its maximum cardinality, the upper LHSI number \(I^{UL}(G)\). We provide formal proofs for the isomorphisms between their line graphs and the original graph structure. We determine the cyclicity and cyclomatic number of the two associated hypergraphs and their relations to the cyclomatic number of the given graph and its line graph are established. Also, we show that the associated vertex hypergraph of an extremal 3-uniform LHSI is conformal and has the Helly property, while the induced edge hypergraph satisfies neither.

32 7

Downloads

Download data is not yet available.

References

[1] B. D. Acharya, Set-valuations of a graph and their applications, MRI Lecture Notes in Applied Mathematics, No. 2, The Mehta Research Institute of Mathematics and Mathematical Physics, Allahabad, (1983).

[2] B. D. Acharya, K. A. Germina and V. Paul, Linear hypergraph set-indexers of a graph, International Mathematical Forum 5(65-68) (2010), 3359 – 3370.

[3] B. D. Acharya and M. L. Vergnas, Hypergraphs with cyclomatic number zero, triangulated graphs, and an inequality, Journal of Combinatorial Theory, Series B 33(1) (1982), 52 – 56, DOI: 10.1016/0095-8956(82)90056-9.

[4] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, (1973).

[5] C. Berge, Hypergraphs: Combinatorics of Finite Sets, North-Holland, Amsterdam, (1989).

[6] C. Biró, J. Lehel and G. Tóth, Helly-Type theorems for the ordering of the vertices of a hypergraph, Order 40 (2023), 665 – 682, DOI: 10.1007/s11083-023-09625-x.

[7] E. Boros, V. Gurvich, M. Milaniˇc and Y. Uno, Conformal hypergraphs: Duality and implications for the upper clique transversal problem, Journal of Graph Theory 109(4) (2025), 466 – 480, DOI: 10.1002/jgt.23238.

[8] F. Dacar, The cyclicity of hypergraphs, Discrete Mathematics 182(1-3) (1998), 53 – 67, DOI: 10.1016/S0012-365X(97)00133-7.

[9] P. C. Gilmore, Families of Sets with Faithful Graph Representations, IBM Research Note, N.C. 184, Thomas J. Watson Research Center, Yorktown Heights, New York, (1962).

[10] L. Lovász, Coverings and colorings of hypergraphs, in: Proceedings of the 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing, pp. 3 – 12, (1973).

[11] V. Paul and K. A. Germina, On uniform linear hypergraph set-indexer of a graph, International Journal of Contemporary Mathematical Sciences 6(17-20) (2011), 861 – 868.

[12] V. Paul and K. A. Germina, On hypergraph coloring and 3-uniform linear hypergraph setindexers of a graph, Discrete Mathematics, Algorithms and Applications 7(2) (2015), 1550015, DOI: 10.1142/S1793830915500159.