Researcher profile

Jonathan Cutler

Jonathan Cutler contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

math.CO

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author

5works

0followers

1topics

3close collaborators

Actions

Decide how to stay connected

Follow researcher0

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

Counting dominating sets and related structures in graphs

We consider some problems concerning the maximum number of (strong) dominating sets in a regular graph, and their weighted analogues. Our primary tool is Shearer's entropy lemma. These techniques extend to a reasonably broad class of graph parameters enumerating vertex colorings satisfying conditions on the multiset of colors appearing in (closed) neighborhoods. We also generalize further to enumeration problems for what we call existence homomorphisms. Here our results are substantially less complete, though we do solve some natural problems.

preprint2014arXiv

A note on the values of independence polynomials at $-1$

The independence polynomial $I(G;x)$ of a graph $G$ is $I(G;x)=\sum_{k=1}^{α(G)} s_k x^k$, where $s_k$ is the number of independent sets in $G$ of size $k$. The decycling number of a graph $G$, denoted $ϕ(G)$, is the minimum size of a set $S\subseteq V(G)$ such that $G-S$ is acyclic. Engström proved that the independence polynomial satisfies $|I(G;-1)| \leq 2^{ϕ(G)}$ for any graph $G$, and this bound is best possible. Levit and Mandrescu provided an elementary proof of the bound, and in addition conjectured that for every positive integer $k$ and integer $q$ with $|q|\leq 2^k$, there is a connected graph $G$ with $ϕ(G)=k$ and $I(G;-1)=q$. In this note, we prove this conjecture.

preprint2014arXiv

Maximal-clique partitions and the Roller Coaster Conjecture

A graph $G$ is {\em well-covered} if every maximal independent set has the same cardinality $q$. Let $i_k(G)$ denote the number of independent sets of cardinality $k$ in $G$. Brown, Dilcher, and Nowakowski conjectured that the independence sequence $(i_0(G), i_1(G), \ldots, i_q(G))$ was unimodal for any well-ordered graph $G$ with independence number $q$. Michael and Traves disproved this conjecture. Instead they posited the so-called ``Roller Coaster" Conjecture: that the terms \[ i_{\left\lceil\frac{q}2\right\rceil}(G), i_{\left\lceil\frac{q}2\right\rceil+1}(G), \ldots, i_q(G) \] could be in any specified order for some well-covered graph $G$ with independence number $q$. Michael and Traves proved the conjecture for $q<8$ and Matchett extended this to $q<12$. In this paper, we prove the Roller Coaster Conjecture using a construction of graphs with a property related to that of having a maximal-clique partition. In particular, we show, for all pairs of integers $1\le k<q$ and positive integers $m$, that there is a well-covered graph $G$ with independence number $q$ for which every independent set of size $k+1$ is contained in a unique maximal independent set, but each independent set of size $k$ is contained in at least $m$ distinct independent sets.

preprint2014arXiv

The maximum number of complete subgraphs of fixed size in a graph with given maximum degree

In this paper, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs $G$ with $n$ vertices and $Δ(G)\leq r$, which has the most complete subgraphs of size $t$, for $t\geq 3$. The conjectured extremal graph is $aK_{r+1}\cup K_b$, where $n=a(r+1)+b$ with $0\leq b\leq r$. Gan, Loh, and Sudakov proved the conjecture when $a\leq 1$, and also reduced the general conjecture to the case $t=3$. We prove the conjecture for $r\leq 6$ and also establish a weaker form of the conjecture for all $r$.

preprint2013arXiv

The maximum number of complete subgraphs in a graph with given maximum degree

Extremal problems involving the enumeration of graph substructures have a long history in graph theory. For example, the number of independent sets in a $d$-regular graph on $n$ vertices is at most $(2^{d+1}-1)^{n/2d}$ by the Kahn-Zhao theorem. Relaxing the regularity constraint to a minimum degree condition, Galvin conjectured that, for $n\geq 2d$, the number of independent sets in a graph with $δ(G)\geq d$ is at most that in $K_{d,n-d}$. In this paper, we give a lower bound on the number of independent sets in a $d$-regular graph mirroring the upper bound in the Kahn-Zhao theorem. The main result of this paper is a proof of a strengthened form of Galvin's conjecture, covering the case $n\leq 2d$ as well. We find it convenient to address this problem from the perspective of $\complement{G}$. In other words, we give an upper bound on the number of complete subgraphs of a graph $G$ on $n$ vertices with $Δ(G)\leq r$, valid for all values of $n$ and $r$.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint