Results 71 to 80 of about 622 (164)
Equitable Coloring ofk-Uniform Hypergraphs [PDF]
SIAM Journal on Discrete Mathematics, 2003 Let $H$ be a $k$-uniform hypergraph with $n$ vertices. A {\em strong $r$-coloring} is a partition of the vertices into $r$ parts, such that each edge of $H$ intersects each part. A strong $r$-coloring is called {\em equitable} if the size of each part is $\lceil n/r \rceil$ or $\lfloor n/r \rfloor$.
openaire +3 more sources
On the Maximum Estrada Index of 3-Uniform Linear Hypertrees
The Scientific World Journal, 2014 For a simple hypergraph H on n vertices, its Estrada index is defined as EE(H)=∑i=1neλi, where λ1,λ2,…,λn are the eigenvalues of its adjacency matrix. In this paper, we determine the unique 3-uniform linear hypertree with the maximum Estrada index.
Faxu Li +4 more
doaj +1 more source
Wickets in 3-uniform hypergraphs
Discrete MathematicsIn these notes, we consider a Turán-type problem in hypergraphs. What is the maximum number of edges if we forbid a subgraph? Let $H_n^{(3)}$ be a 3-uniform linear hypergraph, i.e. any two edges have at most one vertex common. A special hypergraph, called {\em wicket}, is formed by three rows and two columns of a $3 \times 3$ point matrix.
openaire +2 more sources
Equitable Orientations of Sparse Uniform Hypergraphs
The Electronic Journal of Combinatorics, 2016 Caro, West, and Yuster (2011) studied how $r$-uniform hypergraphs can be oriented in such a way that (generalizations of) indegree and outdegree are as close to each other as can be hoped. They conjectured an existence result of such orientations for sparse hypergraphs, of which we present a proof.
Cohen, Nathann, Lochet, William
openaire +4 more sources
Online Matching on 3-Uniform Hypergraphs
The online matching problem was introduced by Karp, Vazirani and Vazirani (STOC 1990) on bipartite graphs with vertex arrivals. It is well-known that the optimal competitive ratio is $1-1/e$ for both integral and fractional versions of the problem.
Sander Borst +2 more
openaire +3 more sources
Maximizing Spectral Radii of Uniform Hypergraphs with Few Edges
Discussiones Mathematicae Graph Theory, 2016 In this paper we investigate the hypergraphs whose spectral radii attain the maximum among all uniform hypergraphs with given number of edges. In particular we characterize the hypergraph(s) with maximum spectral radius over all unicyclic hypergraphs ...
Fan Yi-Zheng +3 more
doaj +1 more source
Discrete Mathematics, 1986 \textit{D. Buset} [Discrete Math. 57, 297-299 (1985; Zbl 0587.05030)] determined for \(k=2\) the sets of all pairs (a,b) such that there exists a k-uniform (connected k-uniform) hypergraph whose automorphism group has exactly a orbits on the set of vertices and b orbits on the set of edges. The author extended this result for arbitrary natural k.
openaire +1 more source
Perfect matchings in 4-uniform hypergraphs
Journal of Combinatorial Theory, Series B, 2016 A perfect matching in a 4-uniform hypergraph is a subset of $\lfloor\frac{n}{4}\rfloor$ disjoint edges. We prove that if $H$ is a sufficiently large 4-uniform hypergraph on $n=4k$ vertices such that every vertex belongs to more than ${n-1\choose 3} - {3n/4 \choose 3}$ edges then $H$ contains a perfect matching.
openaire +3 more sources
Chromatic Coefficients of Linear Uniform Hypergraphs
Journal of Combinatorial Theory, Series B, 1998 Formulae are given for the coefficients of the highest powers of \(\lambda\) in the chromatic polynomial \(P(H,\lambda)\) of a linear uniform \(h\)-hypergraph \(H\), thus generalizing the corresponding result of \textit{G. H. J. Meredith} for graphs [J. Comb. Theory, Ser. B 13, 14-17 (1972; Zbl 0218.05056)]. Some differences appear whenever (\(g= 3\), \
openaire +2 more sources
A note on self-complementary hypergraphs [PDF]
Opuscula Mathematica, 2005 In the paper we describe all self-complementary hypergraphs. It turns out that such hypergraphs exist if and only if the number of vertices of the hypergraph is of the form \(n=2^k\). This answers a conjecture posed by A.
Małgorzata Zwonek
doaj