×

On the spectrum and number of convex sets in graphs. (English) Zbl 1309.05116

Summary: A subset \(S\) of vertices of a graph \(G\) is \(g\)-convex if whenever \(u\) and \(v\) belong to \(S\), all vertices on shortest paths between \(u\) and \(v\) also lie in \(S\). The \(g\)-spectrum of a graph is the set of sizes of its \(g\)-convex sets. In this paper we consider two problems – counting \(g\)-convex sets in a graph, and determining when a graph has \(g\)-convex sets of every cardinality (such graphs are said to have the continuum property). We show that the problem of counting \(g\)-convex sets of a graph whose components have diameter at most 2 is \(\# P\)-complete, but for the class of cographs these sets can be enumerated in linear time. The problem of determining whether or not the \(g\)-convexity of a graph has the continuum property is proven to be NP-complete.
While every graph is shown to be an induced subgraph of a graph whose \(g\)-convexity possesses the continuum property, graphs with the continuum property are rare since for any fixed \(\epsilon \in(0, 1)\) it is shown that almost all \(n\)-vertex graphs have a gap in their \(g\)-spectrum of size at least \(\varOmega(n^{1 - \epsilon})\). Moreover, it is shown that for almost all graphs, every \(g\)-convex set is a clique, from which it follows that the number of \(g\)-convex sets in a random graph is at least \(n^{c \ln n}\) for some constant \(c\). The graph convexity under discussion fits within the class of alignments on a finite set, namely those set systems on a finite set \(V\) that contain the whole set, the empty set, and are closed under intersection. Finite topologies are perhaps the most famous examples of alignments, and our results here are compared and contrasted with what can be said for topologies on a finite set.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C30 Enumeration in graph theory
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Artigas, D.; Dantos, S.; Dourado, M. C.; Szwarcfiter, J. L., Partitioning a graph into convex sets, Discrete Math., 311, 1968-1977 (2011) · Zbl 1223.05220
[2] Bandelt, H.-J.; Mulder, H. M., Distance-hereditary graphs, J. Combin. Theory B, 41, 182-208 (1986) · Zbl 0605.05024
[3] Bodlaender, H. L.; Möhring, R. H., The pathwidth and treewidth of cographs, SIAM J. Discrete Math., 6, 181-188 (1993) · Zbl 0773.05091
[4] Bollobás, B., Random Graphs (1985), Academic Press: Academic Press London · Zbl 0567.05042
[5] Bollobás, B., Graph Theory (1979), Springer: Springer New York · Zbl 0418.05049
[6] Bondy, J. A.; Murty, U. S.R., Graph Theory (2000), Springer: Springer New York · Zbl 1134.05001
[8] Brown, J. I., Discrete Structures and Their Interactions (2013), CRC Press: CRC Press Boca Raton · Zbl 1277.06001
[9] Brown, J. I.; Dilcher, K.; Manna, D., Asymptotics of a sequence of sparse binomial-type polynomials, Analysis, 32, 231-245 (2012) · Zbl 1368.05010
[10] Brown, J. I.; Oellermann, O. R., Graphs with a minimal number of convex sets, Graphs Combin., 30, 1383-1397 (2014) · Zbl 1306.05041
[11] Cáceres, J.; Oellermann, O. R.; Puertas, M. L., Minimal trees and convex geometries, Discuss. Math. Graph Theory, 32, 685-704 (2012) · Zbl 1293.05314
[12] Cohen, S. D., Clique numbers of Paley graphs, Quaestiones Math., 11, 225-231 (1988) · Zbl 0691.05051
[13] Corless, R. M.; Gonnet, G. H.; Hare, D. E.G.; Jeffrey, D. J.; Knuth, D. E., On the Lambert \(W\) function, Adv. Comput. Math., 5, 329-359 (1996) · Zbl 0863.65008
[14] Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L., Complement reducible graphs, Discrete Appl. Math., 3, 163-174 (1981) · Zbl 0463.05057
[15] Dourado, M. C.; Gimbel, J. G.; Kratochvíl, J.; Protti, F.; Szwarcfiter, J. L., On the computation of the hull number of a graph, Discrete Math., 309, 5668-5674 (2009) · Zbl 1215.05184
[16] Dragan, F. F.; Nicolai, F.; Brandstädt, A., Convexity and HHD-free graphs, SIAM J. Discrete Math., 12, 119-135 (1999) · Zbl 0916.05060
[17] Erné, M., Struktur und anzahlformeln für Topologien auf endlichen Mengen, Manuscripta Math., 221-259 (1961) · Zbl 0269.54001
[18] Evans, J. W.; Harary, F.; Lynn, M. S., On the computer enumeration of finite topologies, Commun. ACM, 10, 295-297 (1967) · Zbl 0166.01003
[19] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebr. Discrete Methods, 7, 433-444 (1986) · Zbl 0591.05056
[20] Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58, 301, 13-30 (1963) · Zbl 0127.10602
[21] Kleitman, D.; Rothschild, B., The number of finite topologies, Proc. Amer. Math. Soc., 25, 276-282 (1970) · Zbl 0197.18802
[22] Nielsen, M.; Oellermann, O. R., Steiner trees and convex geometries, SIAM J. Discrete Math., 23, 680-693 (2009) · Zbl 1191.05037
[23] Vadhan, S. P., The complexity of counting in sparse, regular, and planar graphs, SIAM J. Comput., 21, 398-437 (2001) · Zbl 0994.68070
[24] Van de Vel, M. J.L., Theory of Convex Structures (1993), North-Holland: North-Holland Amsterdam · Zbl 0785.52001
[26] Yan, W.; Yeh, Y.-N., Enumeration of subtrees of a tree, Theoret. Comput. Sci., 369, 256-268 (2006) · Zbl 1140.05308
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.