𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Indecomposable regular graphs and hypergraphs

✍ Scribed by Zoltán Füredi

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
390 KB
Volume
101
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Ftiredi, Z&an, Indecomposable regular graphs and hypergraphs, Discrete Mathematics 101 (1992) 59-64. Let G be a d-regular simple graph with n vertices. Here it is proved that for d > 6 -1, G contains a proper regular spanning subhypergraph. The same statement is proved for multigraphs with d > (n -1)/3. These bounds are best possible if d is odd. The main tool of the proof is a consequence of Tutte's f-factor theorem on the existence of 2-factors, due to TaSkinov. Finally, disproving a conjecture of Alon and Berman, an indecomposable d-regular 3-uniform hypergraph is constructed with d 3 2(nm6)'2.

📜 SIMILAR VOLUMES

Cohomomorphisms of graphs and hypergraph
Cohomomorphisms of graphs and hypergraphs
✍ Pavol Hell; Jaroslav Nešetřil 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 547 KB

In addition to a widely studied notion of homomorphisms of graphs and hypergraphs, [2, 5 , 6, 7, 9, 13, 141, we introduce the dual notion of cohomomorphisms. We shall concentrate on only a few aapects of these mappings, mostly with regard to intended applications, [lo, 111. Our basic motivation is t

Graph properties and hypergraph colourin
Graph properties and hypergraph colourings
✍ Jason I. Brown; Derek G. Corneil 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 855 KB

Given a graph property P, graph G and integer k 20, a P k-colouring of G is a function Jr:V(G)+ (1,. . ) k} such that the subgraph induced by each colour class has property P. When P is closed under induced subgraphs, we can construct a hypergraph HG such that G is P k-colourable iff Hg is k-colou

Anti-Hadamard Matrices, Coin Weighing, T
Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs
✍ Noga Alon; Văn H Vũ 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 435 KB

Let / 1 (n) denote the maximum possible absolute value of an entry of the inverse of an n by n invertible matrix with 0,1 entries. It is proved that / 1 (n)=n (1Â2+o(1)) n . This solves a problem of Graham and Sloane. Let m(n) denote the maximum possible number m such that given a set of m coins out

Regular Graphs, Eigenvalues and Regular
Regular Graphs, Eigenvalues and Regular Factors
✍ Hongliang Lu 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB

## Abstract In this article, we obtain a sufficient condition for the existence of regular factors in a regular graph in terms of its third largest eigenvalue. We also determine all values of __k__ such that every __r__‐regular graph with the third largest eigenvalue at most has a __k__‐factor.