Nonuniform subset graphs associated with any graph

Inspired by the study of token graphs and uniform subset graphs, explored by Fabila-Monroy et al. [Token graphs, Graphs Combin. 28 (2012) 365–380. doi:10.1007/s00373-011-1055-9] and Chen and Lih [Hamiltonian uniform subset graphs, J. Combin. Theory Ser. B 42 (1987) 257–263], respectively, we introduce a new graph that seems like a combination of them. Let [Formula: see text] be a graph and [Formula: see text] be an integer. A nonuniform subset graph associated with [Formula: see text] is a graph whose vertex set consists of all [Formula: see text]-subsets of [Formula: see text]. Two vertices are adjacent if and only if their intersection contains at least one edge of [Formula: see text] (each edge of [Formula: see text] is represented as a 2-subset of [Formula: see text]). In this paper, we prove that this graph differs significantly from token graphs and uniform subset graphs. We also investigate its various theoretical graph properties, including the clique number, connectedness, and hamiltonicity.