|
Helly dimension of line graphs of $k$-uniform hypergraphs
E. V. Krylov Belarusian State University
Abstract:
Dependencies of Helly and Krauz dimension are investigated ($r$-mino and line graphs of $k$-uniform hypergraphs, respectively). It is shown that intersection of $r$-mino and line graphs of $k$-uniform hypergraphs classes is not empty for any $r\ge k\ge 2$. It is proven that helly dimension can be computed in a polynomial time against krauz dimension and maximal vertex degree of graph. Boundaries of helly dimension in terms of krauz dimension are given. It is proven that "$kd_s(G)\le 3$" recognition problem is $NP$-complete in the $3$-mino class.
Received: 30.12.2009
Citation:
E. V. Krylov, “Helly dimension of line graphs of $k$-uniform hypergraphs”, Tr. Inst. Mat., 18:2 (2010), 55–59
Linking options:
https://www.mathnet.ru/eng/timb17 https://www.mathnet.ru/eng/timb/v18/i2/p55
|
|