Showing math.COShow all
3 papers · 1 filter
math.CO2026
Efficient Enumeration of Cliques in Graphs with Bounded Maximum Degree
Shi-Cai Gong, Jia-Jin Wang, Xin-Hao Zhu +1
In recent years, there has been a surge of interest in extremal problems concerning the enumeration of independent sets or cliques in graphs with specific constraints. For instance…
math.CO2024
The number of dissociation sets in connected graphs
Bo-Jun Yuan, Ni Yang, Hong-Yan Ge +1
Extremal problems related to the enumeration of graph substructures, such as independent sets, matchings, and induced matchings, have become a prominent area of research with the a…
math.CO2024
Maximal and maximum induced matchings in connected graphs
Bo-Jun Yuan, Zhao-Yu Yang, Lu Zheng +1
An induced matching in a graph is a set of edges whose endpoints induce a -regular subgraph. Gupta et al. (2012,\cite{Gupta}) showed that every -vertex graph has at most $10^…