Source author record

Adriana Hansberg

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.NT

Catalog footprint

Research overview

9works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On zero-sum spanning trees and zero-sum connectivity

We consider $2$ -colourings $f : E(G) \rightarrow \{ -1 ,1 \}$ of the edges of a graph $G$ with colours $-1$ and $1$ in $\mathbb{Z}$ . A subgraph $H$ of $G$ is said to be a zero-sum subgraph of $G$ under $f$ if $f(H) := \sum_{e\in E(H)} f(e) =0$ . We study the following type of questions, in several cases obtaining best possible results: Under which conditions on $|f(G)|$ can we guarantee the existence of a zero-sum spanning tree of $G$ ? The types of $G$ we consider are complete graphs, $K_3$ -free graphs, $d$ -trees, and maximal planar graphs. We also answer the question of when any such colouring contains a zero-sum spanning path or a zero-sum spanning tree of diameter at most $3$ , showing in passing that the diameter- $3$ condition is best possible. Finally, we give, for $G = K_n$ , a sharp bound on $|f(K_n)|$ by which an interesting zero-sum connectivity property is forced, namely that any two vertices are joined by a zero-sum path of length at most $4$ . One feature of this paper is the proof of an Interpolation Lemma leading to a Master Theorem from which many of the above results follow and which can be of independent interest.

preprint2016arXiv

Zero-sum subsequences in bounded-sum $\{-1, 1\}$ -sequences

The following result gives the flavor of this paper: Let $t$ , $k$ and $q$ be integers such that $q\geq 0$ , $0\leq t < k$ and $t \equiv k \,({\rm mod}\, 2)$ , and let $s\in [0,t+1]$ be the unique integer satisfying $s \equiv q + \frac{k-t-2}{2} \,({\rm mod} \, (t+2))$ . Then for any integer $n$ such that $n \ge \max\left\{k,\frac{1}{2(t+2)}k^2 + \frac{q-s}{t+2}k - \frac{t}{2} + s\right\}$ and any function $f:[n]\to \{-1,1\}$ with $|\sum_{i=1}^nf(i)| \le q$ , there is a set $B \subseteq [n]$ of $k$ consecutive integers with $|\sum_{y\in B}f(y)| \le t$ . Moreover, this bound is sharp for all the parameters involved and a characterization of the extremal sequences is given. This and other similar results involving different subsequences are presented, including decompositions of sequences into subsequences of bounded weight.

preprint2015arXiv

Locating-dominating sets and identifying codes in graphs of girth at least 5

Locating-dominating sets and identifying codes are two closely related notions in the area of separating systems. Roughly speaking, they consist in a dominating set of a graph such that every vertex is uniquely identified by its neighbourhood within the dominating set. In this paper, we study the size of a smallest locating-dominating set or identifying code for graphs of girth at least 5 and of given minimum degree. We use the technique of vertex-disjoint paths to provide upper bounds on the minimum size of such sets, and construct graphs who come close to meet these bounds.

preprint2015arXiv

Partial domination - the isolation number of a graph

We prove the following result: If $G$ be a connected graph on $n \ge 6$ vertices, then there exists a set of vertices $D$ with $|D| \le \frac{n}{3}$ and such that $V(G) \setminus N[D]$ is an independent set, where $N[D]$ is the closed neighborhood of $D$ . Furthermore, the bound is sharp. This seems to be the first result in the direction of partial domination with constrained structure on the graph induced by the non-dominated vertices, which we further elaborate in this paper.

preprint2015arXiv

Regular independent sets

The regular independence number, introduced by Albertson and Boutin in 1990, is the size of a largest set of independent vertices with the same degree. Lower bounds were proven for this invariant, in terms of the order, for trees and planar graphs. In this article, we generalize and extend these results to find lower bounds for the regular $k$ -independence number for trees, forests, planar graphs, $k$ -trees and $k$ -degenerate graphs.

preprint2012arXiv

New approach to the $k$ -independence number of a graph

Let $G = (V,E)$ be a graph and $k \ge 0$ an integer. A $k$ -independent set $S \subseteq V$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$ . With $α_k(G)$ we denote the maximum cardinality of a $k$ -independent set of $G$ . We prove that, for a graph $G$ on $n$ vertices and average degree $d$ , $α_k(G) \ge \frac{k+1}{\lceil d \rceil + k + 1} n$ , improving the hitherto best general lower bound due to Caro and Tuza [Improved lower bounds on k-independence, J. Graph Theory 15 (1991), 99-107].

preprint2012arXiv

Partitions of graphs into small and large sets

Let $G$ be a graph on $n$ vertices. We call a subset $A$ of the vertex set $V(G)$ \emph{ $k$ -small} if, for every vertex $v \in A$ , $°(v) \le n - |A| + k$ . A subset $B \subseteq V(G)$ is called \emph{ $k$ -large} if, for every vertex $u \in B$ , $°(u) \ge |B| - k - 1$ . Moreover, we denote by $φ_k(G)$ the minimum integer $t$ such that there is a partition of $V(G)$ into $t$ $k$ -small sets, and by $Ω_k(G)$ the minimum integer $t$ such that there is a partition of $V(G)$ into $t$ $k$ -large sets. In this paper, we will show tight connections between $k$ -small sets, respectively $k$ -large sets, and the $k$ -independence number, the clique number and the chromatic number of a graph. We shall develop greedy algorithms to compute in linear time both $φ_k(G)$ and $Ω_k(G)$ and prove various sharp inequalities concerning these parameters, which we will use to obtain refinements of the Caro-Wei Theorem, the Turán Theorem and the Hansen-Zheng Theorem among other things.

preprint2011arXiv

Degrees in oriented hypergraphs and Ramsey p-chromatic number

The family $D(k,m)$ of graphs having an orientation such that for every vertex $v \in V(G)$ either (outdegree) $°^+(v) \le k$ or (indegree) $°^-(v) \le m$ have been investigated recently in several papers because of the role $D(k,m)$ plays in the efforts to estimate the maximum directed cut in digraphs and the minimum cover of digraphs by directed cuts. Results concerning the chromatic number of graphs in the family $D(k,m)$ have been obtained via the notion of $d$ -degeneracy of graphs. In this paper we consider a far reaching generalization of the family $D(k,m)$ , in a complementary form, into the context of $r$ -uniform hypergraphs, using a generalization of Hakimi's theorem to $r$ -uniform hypergraphs and by showing some tight connections with the well known Ramsey numbers for hypergraphs.

preprint2011arXiv

Fair Domination in Graphs

A fair dominating set in a graph $G$ (or FD-set) is a dominating set $S$ such that all vertices not in $S$ are dominated by the same number of vertices from $S$ ; that is, every two vertices not in $S$ have the same number of neighbors in $S$ . The fair domination number, $fd(G)$ , of $G$ is the minimum cardinality of a FD-set. We present various results on the fair domination number of a graph. In particular, we show that if $G$ is a connected graph of order $n \ge 3$ with no isolated vertex, then $fd(G) \le n - 2$ , and we construct an infinite family of connected graphs achieving equality in this bound. We show that if $G$ is a maximal outerplanar graph, then $fd(G) < 17n/19$ . If $T$ is a tree of order $n \ge 2$ , then we prove that $fd(T) \le n/2$ with equality if and only if $T$ is the corona of a tree.

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.

Adriana Hansberg

Research overview

Is this your work?

9 publications

On zero-sum spanning trees and zero-sum connectivity

Zero-sum subsequences in bounded-sum $\{-1, 1\}$ -sequences

Locating-dominating sets and identifying codes in graphs of girth at least 5

Partial domination - the isolation number of a graph

Regular independent sets

New approach to the $k$ -independence number of a graph

Partitions of graphs into small and large sets

Degrees in oriented hypergraphs and Ramsey p-chromatic number

Fair Domination in Graphs

See the researcher in context

Building this map preview

Adriana Hansberg

Research overview

Is this your work?

9 publications

On zero-sum spanning trees and zero-sum connectivity

Zero-sum subsequences in bounded-sum {−1,1}\{-1, 1\}{−1,1}-sequences

Locating-dominating sets and identifying codes in graphs of girth at least 5

Partial domination - the isolation number of a graph

Regular independent sets

New approach to the kkk-independence number of a graph

Partitions of graphs into small and large sets

Degrees in oriented hypergraphs and Ramsey p-chromatic number

Fair Domination in Graphs

See the researcher in context

Building this map preview

Zero-sum subsequences in bounded-sum $\{-1, 1\}$ -sequences

New approach to the $k$ -independence number of a graph