Independent set and matching permutations
Journal of Graph Theory · 2022-01 · 99 (1) · 40-57
DOI: 10.1002/jgt.22724 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 27.07.2021. Verfasst von Taylor Ball und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 20 Literaturangaben. Gefördert von: Simons Foundation.
Abstract (Originalsprache)
Let be a graph whose largest independent set has size . A permutation of is an independent set permutation of if where is the number of independent sets of size in . In 1987 Alavi, Malde, Schwenk, and Erdős proved that every permutation of is an independent set permutation of some graph with , that is, with the largest independent set having size . They raised the question of determining, for each , the smallest number such that every permutation of is an independent set permutation of some graph with and with at most vertices, and they gave an upper bound on of roughly . Here we settle the question, determining , and make progress on a related question, that of determining the smallest order such that every permutation of is the unique independent set permutation of some graph of at most that order. More generally we consider an extension of independent set permutations to weak orders, and extend Alavi et al.'s main result to show that every weak order on can be realized by the independent set sequence of some graph with and with at most vertices. Alavi et al. also considered matching permutations , defined analogously to independent set permutations. They observed that not every permutation of is a matching permutation of some graph with the largest matching having size , putting an upper bound of on the number of matching permutations of . Confirming their speculation that this upper bound is not tight, we improve it to .
Förderung
- Simons Foundation
Zitieren
APA
Ball, T., Galvin, D., Hyry, C., & Weingartner, K. (2022). Independent set and matching permutations. Journal of Graph Theory, 99(1), 40-57. https://doi.org/10.1002/jgt.22724
Vancouver
Ball T, Galvin D, Hyry C, Weingartner K. Independent set and matching permutations. Journal of Graph Theory. 2022;99(1):40-57. doi:10.1002/jgt.22724
BibTeX
@article{Ball2022,
author = {Ball, Taylor and Galvin, David and Hyry, Catherine and Weingartner, Kyle},
title = {Independent set and matching permutations},
journal = {Journal of Graph Theory},
year = {2022},
volume = {99},
number = {1},
pages = {40--57},
doi = {10.1002/jgt.22724}
}
EUVIMED