Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-07T21:48:45.951Z Has data issue: false hasContentIssue false
  • English
  • Français

Covering Complete r-Graphs with Spanning Complete r-Partite r-Graphs

Published online by Cambridge University Press:  09 February 2011

SEBASTIAN M. CIOABĂ ,
ANDRÉ KÜNDGEN ,
CRAIG M. TIMMONS  and
VLADISLAV V. VYSOTSKY
SEBASTIAN M. CIOABĂ
Affiliation:
Department of Mathematical Sciences, University of Delaware, Newark, DE 19716, USA (e-mail: cioaba@math.udel.edu)
ANDRÉ KÜNDGEN
Affiliation:
Department of Mathematics, California State University San Marcos, San Marcos, CA 92096, USA (e-mail: akundgen@csusm.edu)
CRAIG M. TIMMONS
Affiliation:
Department of Mathematics, University of California San Diego, La Jolla, CA 92093, USA (e-mail: ctimmons@ucsd.edu)
VLADISLAV V. VYSOTSKY
Affiliation:
Department of Mathematical Sciences, University of Delaware, Newark, DE 19716, USA (e-mail: vysotsky@math.udel.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

An r-cut of the complete r-uniform hypergraph Krn is obtained by partitioning its vertex set into r parts and taking all edges that meet every part in exactly one vertex. In other words it is the edge set of a spanning complete r-partite subhypergraph of Krn. An r-cut cover is a collection of r-cuts such that each edge of Krn is in at least one of the cuts. While in the graph case r = 2 any 2-cut cover on average covers each edge at least 2-o(1) times, when r is odd we exhibit an r-cut cover in which each edge is covered exactly once. When r is even no such decomposition can exist, but we can bound the average number of times an edge is cut in an r-cut cover between $1+\frac1{r+1}$ and $1+\frac{1+o(1)}{\log r}$. The upper bound construction can be reformulated in terms of a natural polyhedral problem or as a probability problem, and we solve the latter asymptotically.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 4 , July 2011 , pp. 519 - 527
Copyright
Copyright © Cambridge University Press 2011

References

[1]Alon, N. (1986) Decomposition of the complete r-graph into complete r-partite r-graphs. Graphs Combin. 2 95–100.CrossRefGoogle Scholar
[2]Alon, N. and Spencer, J. (2008) The Probabilistic Method, third edition, Wiley Interscience Series in Discrete Mathematics and Optimization.CrossRefGoogle Scholar
[3]Cioabă, S. M. and Kündgen, A. Covering hypergraphs with cuts of minimum total size. Graphs Combin. (to appear).Google Scholar
[4]Cioabă, S. M., Kündgen, A. and Verstraëte, J. (2009) On decompositions of complete hypergraphs. J. Combin. Theory Ser. A 116 1232–1234.CrossRefGoogle Scholar
[5]Fredman, M. K. and Komlós, J. (1984) On the size of separating systems and families of perfect hash functions. SIAM J. Alg. Discrete Methods 5 61–68.CrossRefGoogle Scholar
[6]Füredi, Z. and Kündgen, A. (2001) Covering a graph with cuts of minimum total size. Discrete Math. 237 129–148.CrossRefGoogle Scholar
[7]Garey, M., Johnson, D. and So, H. (1976) An application of graph coloring to printed circuit testing. IEEE Trans. Circuits and Systems CAS-23 591–599.CrossRefGoogle Scholar
[8]Graham, R. L. and Pollak, H. O. (1971) On the addressing problem for loop switching. Bell System Tech. J. 50 2495–2519.CrossRefGoogle Scholar
[9]Graham, R. L. and Pollak, H. O. (1972) On embedding graphs in squashed cubes. In Graph Theory and Applications, Vol. 303 of Lecture Notes in Mathematics, Springer, pp. 99–110.Google Scholar
[10]Harary, F., Hsu, D. and Miller, Z. (1977) The biparticity of a graph. J. Graph Theory 1 131–133.CrossRefGoogle Scholar
[11]Jaeger, F., Khelladi, A. and Mollard, M. (1985) On shortest cocycle covers of graphs. J. Combin. Theory Ser. B 39 153–163.CrossRefGoogle Scholar
[12]Jamshy, U. and Tarsi, M. (1989) Cycle covering of binary matroids. J. Combin. Theory Ser. B 46 154–161.CrossRefGoogle Scholar
[13]Karlin, S. and Taylor, H. M. (1981) A Second Course in Stochastic Processes, Academic Press.Google Scholar
[14]Klugerman, M., Russell, A. and Sundaram, R. (1998) A note on embedding complete graphs into hypercubes. Discrete Math. 186 289–293.CrossRefGoogle Scholar
[15]Kündgen, A. (1998) Covering cliques with spanning bicliques. J. Graph Theory 27 223–227.3.0.CO;2-P>CrossRefGoogle Scholar
[16]Kündgen, A. and Spangler, M. (2005) A bound on the total size of a cut cover. Discrete Math. 296 121–128.CrossRefGoogle Scholar
[17]Matula, D. W. (1972) k-components, clusters and slicings in graphs. SIAM J. Appl. Math. 22 459–480.CrossRefGoogle Scholar
[18]Mehlhorn, K. (1982) On the program size of perfect functions and universal hash functions. In Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 170–175.CrossRefGoogle Scholar
[19]Nilli, A. (1994) Perfect hashing and probability. Combin. Probab. Comput. 3 407–409.CrossRefGoogle Scholar
[20]Peck, G. W. (1984) A new proof of a theorem of Graham and Pollak. Discrete Math. 49 327–328.CrossRefGoogle Scholar
[21]Radhakrishnan, J. (2001) Entropy and counting. In IIT Kharagpur Golden Jubilee Volume on Computational Mathematics, Modelling and Algorithms (Mishra, J. C., ed.), Narosa, New Delhi.Google Scholar
[22]Tverberg, H. (1982) On the decomposition of K n into complete bipartite graphs. J. Graph Theory 6 493–494.CrossRefGoogle Scholar
[23]Vishwanathan, S. (2008) A polynomial space proof of the Graham–Pollak theorem. J. Combin. Theory Ser. A 115 674–676.CrossRefGoogle Scholar