Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-23T23:23:06.323Z Has data issue: false hasContentIssue false
  • English
  • Français

On r-graphs and r-multihypergraphs with given maximum degree

Part of: Graph theory Designs and configurations

Published online by Cambridge University Press:  09 April 2009

Zoltán Füredi
Zoltán Füredi
Affiliation:
Mathematical InstituteHungarian Academy of Sciences 1364 Budapest POB 127, Hungary
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.

It is well-known that if G is a multigraph (that is, a graph with multiple edges), the maximum number of pairwise disjoint edges in G is ν(G) and its maximum degree is D(G), then |E(G)| ≤ ν [3D/2’. We extend this theorem for r-graphs (that is, families of r-element sets) and for r-multihypergraphs (that is, r-graphs with repeated edges). Several problems remain open.

MSC classification

Secondary: 05C65: Hypergraphs 05B40: Packing and covering
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 50 , Issue 2 , April 1991 , pp. 204 - 212
Copyright
Copyright © Australian Mathematical Society 1991

References

[1]Abbott, H. L., Hanson, D. and Liu, A. C., ‘An extremal problem in graph theory,’ Quart. J. Math. Oxford Soc. (2) 31 (1980), 1–7.Google Scholar
[2]Abbott, H. L., Hanson, D. and Liu, A. C., ‘An extremal problem in hypergraph theory II,’ J. Austral. Math. Soc. Ser. A 31 (1981), 129–135.Google Scholar
[3]Abbott, H. L., Hanson, D. and Sauer, N., ‘Intersection theorems for systems of sets’,J. Combin. Theory Ser. A 12 (1972), 381–389.Google Scholar
[4]Abbott, H. L., Katchalski, M. and Liu, A. C., ‘An extremal problem in hypergraph theory,’ Discrete Math. Analysis and Comb. Comp., (1980), Conference Proceedings, School of Computer Science, Univ. New Brunswick, Fredericton, pp. 74–82.Google Scholar
[5]Abbott, H. L., Katchaiski, M. and Liu, A. C., ‘An extremal problem in graph theory II’, J. Austral. Math. Soc. Ser.A 29 (1980), 417–424.Google Scholar
[6]Bermond, J.-C. and Bond, J., ‘Combinatorial designs and hypergraphs of diameter one’, Proc. First China-USA Conf. on Graph Theory, (1986).Google Scholar
[7]Bermond, J.-C., Bond, J., Paoli, M. and Peyrat, C., ‘Graphs and interconnection networks: diameter and vulnerability’, Surveys in Combinatorics (Lloyd, E. K., ed.), London Math. Soc. Lecture Notes 82, Cambridge, 1983, pp. 1–30.Google Scholar
[8]Bermond, J.-C., Bond, J. and Saclé, J. F., ‘Large hypergraphs of diameter1’, Graph Theory and Combinatorics (Cambridge, 1983), pp. 19–28 (Academic Press, London, New York, 1984).Google Scholar
[9]Bollobás, B., ‘Extremal problems in graph theory’, J. Graph Theory 1 (1977), 117–123.Google Scholar
[10]Bollobás, B., ‘Disjoint triples in a 3-graph with given maximal degree’, Quart J.Math. Oxford Ser. (2) 28 (1977), 81–85.Google Scholar
[11]Bollobás, B., Extremal graph theory, (Academic Press, London, 1978).Google Scholar
[12]Chung, F. R. K., Füredi, Z., Garey, M. R. and Graham, R. L., ‘On the fractional covering number of hypergraphs’, SIAM J. Disc. Math. 1 (1988), 45–49.CrossRefGoogle Scholar
[13]Chvátal, V. and Hanson, D., ‘Degrees and matchings’, J. Combin. Theory Ser. B 20 (1976), 128–138.CrossRefGoogle Scholar
[14]Erdös, P. and Rado, R., ‘Intersection theorems for systems of sets’, J. London Math. Soc. 35 (1960), 85–90.Google Scholar
[15]Faber, V. and Lovász, L., ‘Problem 18 in Hypergraph Seminar’, Proc. First Working Seminar, Columbus, Ohio, 1972, edited by Berge, C. and Ray-Chaudhuri, D. K., p. 284 (Lecture Notes in Math. 411, Springer-Verlag, Berlin, 1974).Google Scholar
[16]Frankl, P. and Füredi, Z., ‘Disjoint r-triples in an r-graph with given maximum degree’, Quart J. Math. Oxford (2) 34 (1983), 423–426.CrossRefGoogle Scholar
[17]Füredi, Z., ‘Maximum degree and fractional matchings in uniform hypergraphs’, Combinatorica 1 (1981), 155–162.Google Scholar
[18]Sauer, N., ‘The largest number of edges of a graph such that not more than g intersect at a point and not more than n are independent’, Combinatorial Math. and Appl., Proc. Conf. Oxford, 1969, edited by Welsh, D. J., ed., pp. 253–257, (Academic Press, London, 1971).Google Scholar
[19]Wilson, R. M., ‘An existence theory for pairwise balanced designs I-III’, J. Combin. Theory Ser. A 13 (1972), 220–273 and 18 (1975), 71–79.Google Scholar