Source author record

Felix Goldberg

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

ResearcherUnclaimed source record

math.CO Computer Science and Game Theory Discrete Mathematics

Catalog footprint

Research overview

14works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Conjectured bounds for the sum of squares of positive eigenvalues of a graph

A well known upper bound for the spectral radius of a graph, due to Hong, is that $μ_1^2 \le 2m - n + 1$ . It is conjectured that for connected graphs $n - 1 \le s^+ \le 2m - n + 1$ , where $s^+$ denotes the sum of the squares of the positive eigenvalues. The conjecture is proved for various classes of graphs, including bipartite, regular, complete $q$ -partite, hyper-energetic, and barbell graphs. Various searches have found no counter-examples. The paper concludes with a brief discussion of the apparent difficulties of proving the conjecture in general.

preprint2014arXiv

A lower bound on the entries of the principal eigenvector of a graph

We obtain a lower bound on each entry of the principal eigenvector of a non-regular connected graph.

preprint2014arXiv

Chip-firing may be much faster than you think

A new bound (Theorem \ref{thm:main}) for the duration of the chip-firing game with $N$ chips on a $n$ -vertex graph is obtained, by a careful analysis of the pseudo-inverse of the discrete Laplacian matrix of the graph. This new bound is expressed in terms of the entries of the pseudo-inverse. It is shown (Section 5) to be always better than the classic bound due to Bj{ö}rner, Lovász and Shor. In some cases the improvement is dramatic. For instance: for strongly regular graphs the classic and the new bounds reduce to $O(nN)$ and $O(n+N)$ , respectively. For dense regular graphs - $d=(\frac{1}{2}+ε)n$ - the classic and the new bounds reduce to $O(N)$ and $O(n)$ , respectively. This is a snapshot of a work in progress, so further results in this vein are in the works.

preprint2014arXiv

Domination in designs

We commence the study of domination in the incidence graphs of combinatorial designs. Let $D$ be a combinatorial design and denote by $γ(D)$ the domination number of the incidence (Levy) graph of $D$ . We obtain a number of results about the domination numbers of various kinds of designs. For instance, a finite projective plane of order $n$ , which is a symmetric $(n^{2}+n+1,n+1,1)$ -design, has $γ=2n$ . %We also show that for any symmetric $(v,k,λ)$ -design it holds that $γ\leq 2k$ . We study at depth the domination numbers of Steiner systems and in particular of Steiner triple systems. We show that a $STS(v)$ has $γ\geq \frac{2}{3}v-1$ and also obtain a number of upper bounds. The tantalizing conjecture that all Steiner triple systems on $v$ vertices have the same domination number is proposed and is verified up to $v \leq 15$ . The structure of minimal dominating sets is also investigated, both for its own sake and as a tool in deriving lower bounds on $γ$ . Finally, a number of open questions are proposed.

preprint2014arXiv

Graph energy estimates via the Chebyshev functional

Let $G$ be a graph with $n$ vertices and $m$ edges. The energy $E$ of the graph $G$ is defined as the sum of the moduli of the adjacency eigenvalues $λ_{1} \geq λ_{2} \geq \ldots \geq λ_{n}$ of $G$ : $E=\sum_{i=1}^{n}{|λ{i}|}.$ We obtain new lower bounds on the energy of a graph, which in various cases improve upon known results. For example, a particularly simple and appealing corollary of our results is: $E \geq \frac{2m}{λ_{1}}.$ This implies a result obtained by Gutman \emph{et al.} for regular graphs and is better for triangle-free graphs than a result of Caporossi \emph{et al.}.

preprint2014arXiv

New results on eigenvalues and degree deviation

Let $G$ be a graph. In a famous paper Collatz and Sinogowitz had proposed to measure its deviation from regularity by the difference of the (adjacency) spectral radius and the average degree: $ε(G)=ρ(G)-\frac{2m}{n}$ . We obtain here a new upper bound on $ε(G)$ which seems to consistently outperform the best known upper bound to date, due to Nikiforov. The method of proof may also be of independent interest, as we use notions from numerical analysis to re-cast the estimation of $ε(G)$ as a special case of the estimation of the difference between Rayleigh quotients of proximal vectors.

preprint2014arXiv

On split graphs with four distinct eigenvalues

It is a well-known fact that a graph of diameter $d$ has at least $d+1$ eigenvalues. Let us call a graph \emph{ $d$ -extremal} if it has diameter $d$ and exactly $d+1$ eigenvalues. Such graphs have been intensively studied by various authors. %Much attention has been devoted to the study of graphs that are extremal with respect to this relation: \emph{i.e} have diameter $d$ and exactly $d+1$ distinct eigenvalues. A graph is \emph{split} if its vertex set can be partitioned into a clique and a stable set. Such a graph has diameter at most $3$ . We obtain a complete classification of the connected bidegreed $3$ -extremal split graphs. We also show how to construct certain families of non-bidegreed $3$ -extremal split graphs.

preprint2014arXiv

On the maximum angle between copositive matrices

Hiriart-Urruty and Seeger have posed the problem of finding the maximal possible angle $θ_{\max}(\mathcal{C}_{n})$ between two copositive matrices of order $n$ . They have proved that $θ_{\max}(\mathcal{C}_{2})=\frac{3}{4}π$ and conjectured that $θ_{\max}(\mathcal{C}_{n})$ is equal to $\frac{3}{4}π$ for all $n \geq 2$ . In this note we disprove their conjecture by showing that $\lim_{n \rightarrow \infty}{θ_{\max}(\mathcal{C}_{n})}=π$ . Our proof uses a construction from algebraic graph theory. We also consider the related problem of finding the maximal angle between a nonnegative matrix and a positive semidefinite matrix of the same order.

preprint2014arXiv

Spectral radius minus average degree: a better bound

Collatz and Sinogowitz had proposed to measure the departure of a graph $G$ from regularity by the difference of the (adjacency) spectral radius and the average degree: $ε(G)=ρ(G)-\frac{2m}{n}$ . We give here new lower bounds on this quantity, which improve upon the currently known ones.

preprint2013arXiv

A spectral bound for graph irregularity

The imbalance of an edge $e=\{u,v\}$ in a graph is defined as $i(e)=|d(u)-d(v)|$ , where $d(\cdot)$ is the vertex degree. The irregularity $I(G)$ of $G$ is then defined as the sum of imbalances over all edges of $G$ . This concept was introduced by Albertson who proved that $I(G) \leq \frac{n^{3}}{27}$ (where $n=|V(G)|$ ) and obtained stronger bounds for bipartite and triangle-free graphs. Since then a number of additional bounds were given by various authors. In this paper we prove a new upper bound, which improves a bound found by Zhou and Luo in 2011. Our bound involves the Laplacian spectral radius $λ$ .

preprint2013arXiv

On monotonicity-preserving perturbations of $M$ -matrices

We obtain an explicit analytical sufficient condition on $E$ that ensures the monotonicity of the matrix $M+E$ , where $M$ is an $M$ -matrix.

preprint2013arXiv

On the sign patterns of the smallest signless Laplacian eigenvector

Let $H$ be a connected bipartite graph, whose signless Laplacian matrix is $Q(H)$ . Suppose that the bipartition of $H$ is $(S,T)$ and that $x$ is the eigenvector of the smallest eigenvalue of $Q(H)$ . It is well-known that $x$ is positive and constant on $S$ , and negative and constant on $T$ . The resilience of the sign pattern of $x$ under addition of edges into the subgraph induced by either $S$ or $T$ is investigated and a number of cases in which the sign pattern of $x$ persists are described.

preprint2013arXiv

Zero forcing for sign patterns

We introduce a new variant of zero forcing - signed zero forcing. The classical zero forcing number provides an upper bound on the maximum nullity of a matrix with a given graph (i.e. zero-nonzero pattern). Our new variant provides an analo- gous bound for the maximum nullity of a matrix with a given sign pattern. This allows us to compute, for instance, the maximum nullity of a Z-matrix whose graph is L(K_{n}), the line graph of a clique.

preprint2008arXiv

The Colin de Verdière Graph Parameter for Threshold Graphs

We consider Schrödinger operators on threshold graphs and prove a formula for the Colin de Verdière parameter in terms of the building sequence. We construct an optimal Colin de Verdière matrix for each connected threshold graph $G$ of $n$ vertices. For a large subclass of threshold graphs we construct an alternative Colin de Verdière matrix depending on a large parameter. As a corollary to this last construction, we give estimates on the size of the non-zero eigenvalues of this matrix.

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.

Felix Goldberg

Research overview

Is this your work?

14 publications

Conjectured bounds for the sum of squares of positive eigenvalues of a graph

A lower bound on the entries of the principal eigenvector of a graph

Chip-firing may be much faster than you think

Domination in designs

Graph energy estimates via the Chebyshev functional

New results on eigenvalues and degree deviation

On split graphs with four distinct eigenvalues

On the maximum angle between copositive matrices

Spectral radius minus average degree: a better bound

A spectral bound for graph irregularity

On monotonicity-preserving perturbations of $M$ -matrices

On the sign patterns of the smallest signless Laplacian eigenvector

Zero forcing for sign patterns

The Colin de Verdière Graph Parameter for Threshold Graphs

See the researcher in context

Building this map preview

Felix Goldberg

Research overview

Is this your work?

14 publications

Conjectured bounds for the sum of squares of positive eigenvalues of a graph

A lower bound on the entries of the principal eigenvector of a graph

Chip-firing may be much faster than you think

Domination in designs

Graph energy estimates via the Chebyshev functional

New results on eigenvalues and degree deviation

On split graphs with four distinct eigenvalues

On the maximum angle between copositive matrices

Spectral radius minus average degree: a better bound

A spectral bound for graph irregularity

On monotonicity-preserving perturbations of MMM-matrices

On the sign patterns of the smallest signless Laplacian eigenvector

Zero forcing for sign patterns

The Colin de Verdière Graph Parameter for Threshold Graphs

See the researcher in context

Building this map preview

On monotonicity-preserving perturbations of $M$ -matrices