Page 1 Next

Displaying 1 – 20 of 194

Showing per page

A backward selection procedure for approximating a discrete probability distribution by decomposable models

Francesco M. Malvestuto (2012)


Decomposable (probabilistic) models are log-linear models generated by acyclic hypergraphs, and a number of nice properties enjoyed by them are known. In many applications the following selection problem naturally arises: given a probability distribution p over a finite set V of n discrete variables and a positive integer k , find a decomposable model with tree-width k that best fits p . If is the generating hypergraph of a decomposable model and p is the estimate of p under the model, we can measure...

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Yury Metelsky, Kseniya Schemeleva, Frank Werner (2017)

Discussiones Mathematicae Graph Theory

We characterize the class [...] L32 L 3 2 of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 L 3 2 in the class of threshold graphs, where n is the number of vertices of a tested graph.

A maximum degree theorem for diameter-2-critical graphs

Teresa Haynes, Michael Henning, Lucas Merwe, Anders Yeo (2014)

Open Mathematics

A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where n 0 is a...

A Note on a Broken-Cycle Theorem for Hypergraphs

Martin Trinks (2014)

Discussiones Mathematicae Graph Theory

Whitney’s Broken-cycle Theorem states the chromatic polynomial of a graph as a sum over special edge subsets. We give a definition of cycles in hypergraphs that preserves the statement of the theorem there

A note on Möbius inversion over power set lattices

Klaus Dohmen (1997)

Commentationes Mathematicae Universitatis Carolinae

In this paper, we establish a theorem on Möbius inversion over power set lattices which strongly generalizes an early result of Whitney on graph colouring.

A note on packing of two copies of a hypergraph

Monika Pilśniak, Mariusz Woźniak (2007)

Discussiones Mathematicae Graph Theory

A 2-packing of a hypergraph 𝓗 is a permutation σ on V(𝓗) such that if an edge e belongs to 𝓔(𝓗), then σ (e) does not belong to 𝓔(𝓗). We prove that a hypergraph which does not contain neither empty edge ∅ nor complete edge V(𝓗) and has at most 1/2n edges is 2-packable. A 1-uniform hypergraph of order n with more than 1/2n edges shows that this result cannot be improved by increasing the size of 𝓗.

A note on perfect matchings in uniform hypergraphs with large minimum collective degree

Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht, Endre Szemerédi (2008)

Commentationes Mathematicae Universitatis Carolinae

For an integer k 2 and a k -uniform hypergraph H , let δ k - 1 ( H ) be the largest integer d such that every ( k - 1 ) -element set of vertices of H belongs to at least d edges of H . Further, let t ( k , n ) be the smallest integer t such that every k -uniform hypergraph on n vertices and with δ k - 1 ( H ) t contains a perfect matching. The parameter t ( k , n ) has been completely determined for all k and large n divisible by k by Rödl, Ruci’nski, and Szemerédi in [Perfect matchings in large uniform hypergraphs with large minimum collective degree, submitted]....

A prime factor theorem for a generalized direct product

Wilfried Imrich, Peter F. Stadler (2006)

Discussiones Mathematicae Graph Theory

We introduce the concept of neighborhood systems as a generalization of directed, reflexive graphs and show that the prime factorization of neighborhood systems with respect to the the direct product is unique under the condition that they satisfy an appropriate notion of thinness.

Currently displaying 1 – 20 of 194

Page 1 Next