Source author record

Simon Jäger

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Exponential Independence

For a set $S$ of vertices of a graph $G$ , a vertex $u$ in $V(G)\setminus S$ , and a vertex $v$ in $S$ , let ${\rm dist}_{(G,S)}(u,v)$ be the distance of $u$ and $v$ in the graph $G-(S\setminus \{ v\})$ . Dankelmann et al. (Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883) define $S$ to be an exponential dominating set of $G$ if $w_{(G,S)}(u)\geq 1$ for every vertex $u$ in $V(G)\setminus S$ , where $w_{(G,S)}(u)=\sum\limits_{v\in S}\left(\frac{1}{2}\right)^{{\rm dist}_{(G,S)}(u,v)-1}$ . Inspired by this notion, we define $S$ to be an exponential independent set of $G$ if $w_{(G,S\setminus \{ u\})}(u)<1$ for every vertex $u$ in $S$ , and the exponential independence number $α_e(G)$ of $G$ as the maximum order of an exponential independent set of $G$ . Similarly as for exponential domination, the non-local nature of exponential independence leads to many interesting effects and challenges. Our results comprise exact values for special graphs as well as tight bounds and the corresponding extremal graphs. Furthermore, we characterize all graphs $G$ for which $α_e(H)$ equals the independence number $α(H)$ for every induced subgraph $H$ of $G$ , and we give an explicit characterization of all trees $T$ with $α_e(T)=α(T)$ .

preprint2016arXiv

Hereditary Equality of Domination and Exponential Domination

We characterize a large subclass of the class of those graphs $G$ for which the exponential domination number of $H$ equals the domination number of $H$ for every induced subgraph $H$ of $G$ .

preprint2016arXiv

Large Values of the Clustering Coefficient

A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (Collective dynamics of `small-world' networks, Nature 393 (1998) 440-442), is the clustering coefficient of a graph $G$ . It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex $u$ of $G$ is the relative density $m(G[N_G(u)])/{d_G(u)\choose 2}$ of its neighborhood if $d_G(u)$ is at least $2$ , and $0$ otherwise. It is unknown which graphs maximize the clustering coefficient among all connected graphs of given order and size. We determine the maximum clustering coefficients among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order. In both cases, we characterize all extremal graphs. Furthermore, we determine the maximum increase of the clustering coefficient caused by adding a single edge.

preprint2016arXiv

Relating Domination, Exponential Domination, and Porous Exponential Domination

The domination number $γ(G)$ of a graph $G$ , its exponential domination number $γ_e(G)$ , and its porous exponential domination number $γ_e^*(G)$ satisfy $γ_e^*(G)\leq γ_e(G)\leq γ(G)$ . We contribute results about the gaps in these inequalities as well as the graphs for which some of the inequalities hold with equality. Relaxing the natural integer linear program whose optimum value is $γ_e^*(G)$ , we are led to the definition of the fractional porous exponential domination number $γ_{e,f}^*(G)$ of a graph $G$ . For a subcubic tree $T$ of order $n$ , we show $γ_{e,f}^*(T)=\frac{n+2}{6}$ and $γ_e(T)\leq 2γ_{e,f}^*(T)$ . We characterize the two classes of subcubic trees $T$ with $γ_e(T)=γ_{e,f}^*(T)$ and $γ(T)=γ_e(T)$ , respectively. Using linear programming arguments, we establish several lower bounds on the fractional porous exponential domination number in more general settings.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Simon Jäger

Research overview

Is this your work?

4 publications

Exponential Independence

Hereditary Equality of Domination and Exponential Domination

Large Values of the Clustering Coefficient

Relating Domination, Exponential Domination, and Porous Exponential Domination

See the researcher in context

Building this map preview