Back to Search
Start Over
The average order of a connected induced subgraph of a graph and union‐intersection systems.
- Source :
-
Journal of Graph Theory . Aug2023, p1. 15p. 1 Illustration, 1 Chart. - Publication Year :
- 2023
-
Abstract
- Because connectivity is such a basic concept in graph theory, extremal problems concerning the average order of the connected induced subgraphs of a graph have been of notable interest. A particularly resistant open problem is whether or not, for a connected graph G $G$ of order n $n$, all of whose vertices have degree at least 3, this average is at least n ∕ 2 $n\unicode{x02215}2$. It is shown in this paper that if G $G$ is a connected, vertex transitive graph, then the average order of the connected induced subgraphs of G $G$ is at least n ∕ 2 $n\unicode{x02215}2$.The extremal graph theory problems mentioned above lead to a broader theory. The concept of a Union‐Intersection System (UIS) S ≔(P , B ) ${\mathscr{S}}:= (P,{\rm{ {\mathcal B} }})$ is introduced, P $P$ being a finite set of points and B ${\rm{ {\mathcal B} }}$ a set of subsets of P $P$ called blocks satisfying the following simple property for all A , B ∈ B $A,B\in {\rm{ {\mathcal B} }}$: if A ∩ B ∈ B $A\cap B\in {\rm{ {\mathcal B} }}$, then A ∪ B ∈ B $A\cup B\in {\rm{ {\mathcal B} }}$. To generalize results on the average order of a connected induced subgraph of a graph, it is conjectured that if a UIS is, in various senses, “connected and regular,” then the average size of a block is at least half the number of points. We prove that if a union‐intersection set system is regular, completely irreducible, and nonredundant, then the average size of a block is at least half the number of points. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03649024
- Database :
- Academic Search Index
- Journal :
- Journal of Graph Theory
- Publication Type :
- Academic Journal
- Accession number :
- 169818826
- Full Text :
- https://doi.org/10.1002/jgt.23024