Connected-Intersecting Families of Graphs

MaRDI QIDQ6312071zbMATH OpenFDO

Authors Aaron Berger, Ross Berkowitz, Pat Devlin, Michael Doppelt, Sonali Durham, Tessa Murthy, Harish Vemuri

Publication date 6 January 2019

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal set theory (05D05) Combinatorial optimization (90C27)

Abstract: For a graph property $mathcalP$ and a common vertex set $V=1,2,ldots,n$, a family of graphs on $V$ is emph{$mathcalP$-intersecting} iff $GcapH$ satisfies $mathcalP$ for all $G,H$ in the family. Addressing a question of Chung, Graham, Frankl, and Shearer, we explore---for various $mathcalP$---the maximum cardinality among all $mathcalP$-intersecting families of graphs. In the connected-intersecting case, we resolve the question completely by a short linear algebraic proof showing this maximum is attained by taking all graphs containing a fixed spanning tree (though we show other extremal constructions as well). We also present a new lower bound for containing unions of a fixed subgraph.

This page was built for publication: Connected-Intersecting Families of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6312071)