Some Properties of Edge-intersection Graph of 3-uniform Hypergraphs of Order 6n and Size 4n

Main Article Content

Supawan Nanta
Krittawit Limkul


Let  gif.latex?\dpi{100}&space;H=(V,E) be a gif.latex?3-uniform, gif.latex?2-regular, connected hypergraph of order gif.latex?6n and size gif.latex?4n for some gif.latex?n&space;\in&space;\mathbb{N}. For gif.latex?e&space;\in&space;E, let gif.latex?E_e=\{f\in&space;E&space;\backslash\{e\}:e\cap&space;f\neq\O\}, the transversal number of a hypergraph gif.latex?H in which gif.latex?|E_e|=2 for all gif.latex?e\in&space;E are investigated. In this paper, we interested in studying some properties of an edge-intersection graph gif.latex?L(H) of a hypergraph gif.latex?H such as the vertex cover, the matching, and the independent set. We prove that  gif.latex?L(H) is a bipartite graph and the transversal number of gif.latex?H is equal to the vertex covering number of gif.latex?L(H).

Article Details



Alain, B. (2013). Hypergraph Theory An Introduction. Switzerland: Springer International Publishing.

Baranyai, Zs. (1975). On the factorization of the complete uniform hypergraph. In Hajnal, A. Rado, R. & Sós, V. T. (eds.), Infinite and Finite Sets. Colloquium held at Keszthely, June 25-July 1, 1973. Dedicated to Paul Erdös on his 60th Birthday (pp. 91-108). Amsterdam, Netherlands: North-Holland.

Bouchou, A. & Blidia, M. (2014). On the k-independence number in graphs. Australasian Journal of Combinatorics 59 (2), 311–322.

Bujtas, Cs., Henning, M. A. & Tuza, Zs. (2012). Transversals and domination in uniform hypergraphs. European Journal of Combinatorics 33, 62-71.

Chvatal, V. & McDiarmid, C. (1992). Small transversals in hypergraphs. Combinatorica 12, 19-26.

Cockayne, E. J., Hedetniemi, S. T. & Slater, P. J. (1979). Matchings and transversals in hypergraphs, domination and independence-in trees. Journal of Combinatorial Theory, Series B 27, 78-80.

Diestel, R. (2000). Graph Theory. New York: Springer-Verlag.

Harant, J. & Rautenbach, D. (2011). Independence in connected graphs. Discrete Applied Math 159 (1), 79-86.

Henning, M. A., Lowenstein, C. & Rautenbach, D. (2012). Independent sets and matchings in subcubic graphs. Discrete Mathematics 312 (11), 1900-1910.

Henning, M. A. & Yeo, A. (2008). Hypergraphs with large transversal number and with edge sizes at least three. Journal of Graph Theory 59, 326-348.

Zhang, Z. & Lou, D. (2009). Notes on bipartite graphs with a perfect matching and digraph. Advances and Applications in Discrete Mathematics 3 (2), 155-164.