Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-30T19:41:01.209Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal induced universal graphs for bounded-degree graphs

Published online by Cambridge University Press:  11 October 2017

NOGA ALON  and
RAJKO NENADOV
NOGA ALON
Affiliation:
Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. e-mail: [email protected]
RAJKO NENADOV
Affiliation:
School of Mathematical Sciences, Monash University, VIC 3800, Australia. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that for any constant Δ ≥ 2, there exists a graph Γ with O(nΔ / 2) vertices which contains every n-vertex graph with maximum degree Δ as an induced subgraph. For odd Δ this significantly improves the best-known earlier bound and is optimal up to a constant factor, as it is known that any such graph must have at least Ω(nΔ/2) vertices.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 166 , Issue 1 , January 2019 , pp. 61 - 74
Copyright
Copyright © Cambridge Philosophical Society 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Research supported in part by a USA-Israeli BSF grant 2012/107, by an ISF grant 620/13 and by the Israeli I-Core program.

References

REFERENCES

[1] Abrahamsen, M., Alstrup, S., Holm, J., Knudsen, M. B. T. and Stöckel, M. Near-optimal induced universal graphs for bounded degree graphs. Preprint. arXiv:1607.04911.Google Scholar
[2] Adjiashvili, D. and Rotbart, N. Labeling schemes for bounded degree graphs. In Proc. 41st Int. Colloq. on Automata, Languages and Programming, Part II (Springer, Berlin Heidelberg, 2014), pp. 375–386.Google Scholar
[3] Alon, N. Asymptotically optimal induced universal graphs. Preprint.Google Scholar
[4] Alon, N. and Capalbo, M. Sparse universal graphs for bounded-degree graphs. Random Structures Algorithms 31 (2) (2007), 123–133.Google Scholar
[5] Alon, N. and Capalbo, M. Optimal universal graphs with deterministic embedding. In Proc. 19th Annu. ACM-SIAM Symp. Discrete Algorithms (Society for Industrial and Applied Mathematics, 2008), pp. 373–378.Google Scholar
[6] Alon, N., Capalbo, M., Kohayakawa, Y., Rödl, V., Ruciński, A. and Szemerédi, E. Near-optimum universal graphs for graphs with bounded degrees. In Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques (Springer, 2001), pp. 170–180.Google Scholar
[7] Alon, N. and Spencer, J. H. The Probabilistic Method (Fourth Edition) (John Wiley and Sons, 2008).Google Scholar
[8] Alstrup, S., Dahlgaard, S. and Knudsen, M. B. T. Optimal induced universal graphs and adjacency labeling for trees. In Proc. 56th Annu. IEEE Symp. on Foundations of Computer Science (IEEE, 2015), pp. 1311–1326.Google Scholar
[9] Alstrup, S., Kaplan, H., Thorup, M. and Zwick, U. Adjacency labeling schemes and induced-universal graphs. In Proc. 47th Annu. ACM Symp. on Theory of Computing (ACM, 2015), pp. 625–634.Google Scholar
[10] Alstrup, S. and Rauhe, T. Small induced-universal graphs and compact implicit graph representations. In Proc. 43rd Annu. IEEE Symp. on Foundations of Computer Science (IEEE, 2002), pp. 53–62.Google Scholar
[11] Butler, S. Induced-universal graphs for graphs with bounded maximum degree. Graphs Combin. 25 (4) (2009), 461–468.Google Scholar
[12] Chung, F. R. Universal graphs and induced-universal graphs. J. Graph Theory 14 (4) (1990), 443–454.Google Scholar
[13] Davidoff, G., Sarnak, P. and Valette, A. Elementary Number Theory, Group Theory and Ramanujan Graphs, vol. 55 (Cambridge University Press, 2003).Google Scholar
[14] Esperet, L., Labourel, A. and Ochem, P. On induced-universal graphs for the class of bounded-degree graphs. Inform. Process. Lett. 108 (5) (2008), 255–260.Google Scholar
[15] Gavoille, C. and Labourel, A. Shorter implicit representation for planar graphs and bounded treewidth graphs. In Proc. European Symp. on Algorithms (Springer, 2007), pp. 582–593.Google Scholar
[16] Kannan, S., Naor, M. and Rudich, S. Implicit representation of graphs. SIAM J. Discrete Math. 5 (4) (1992), 596–603.Google Scholar
[17] Lovász, L. and Plummer, M. D. Matching theory, vol. 367 (American Mathematical Soc., 2009).Google Scholar
[18] Lubotzky, A., Phillips, R. and Sarnak, P. Ramanujan graphs. Combinatorica 8 (3) (1988), 261–277.Google Scholar
[19] Margulis, G. A. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problemy peredachi informatsii 24 (1) (1988), 51–60.Google Scholar
[20] Moon, J. W. On minimal n-universal graphs. Proc. Glasgow Mathematical Assoc. 7 (1) (1965), 32–33.Google Scholar
[21] Rado, R. Universal graphs and universal functions. Acta Arith. 4 (9) (1964), 331–340.Google Scholar
[22] Vizing, V. G. Some unsolved problems in graph theory. Russian Math. Surveys 23 (6) (1988), 125–141.Google Scholar