Source author record

John Sinkovic

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

7works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Graphs with few trivial characteristic ideals

We give a characterization of the graphs with at most three trivial characteristic ideals. This implies the complete characterization of the regular graphs whose critical groups have at most three invariant factors equal to 1 and the characterization of the graphs whose Smith groups have at most 3 invariant factors equal to 1. We also give an alternative and simpler way to obtain the characterization of the graphs whose Smith groups have at most 3 invariant factors equal to 1, and a list of minimal forbidden graphs for the family of graphs with Smith group having at most 4 invariant factors equal to 1.

preprint2016arXiv

A graph for which the inertia bound is not tight

The inertia bound gives an upper bound on the independence number of a graph by considering the inertia of matrices corresponding to the graph. The bound is known to be tight for graphs on 10 or fewer vertices as well as for all perfect graphs. The question has been asked as to whether the bound is always tight. We show that the bound is not tight for the Paley graph on 17 vertices as well as for the graph obtained from Paley 17 by deleting a vertex.

preprint2016arXiv

Minimal obstructions for tree-depth: A non-1-unique example

A k-ranking of a graph G is a labeling of the vertices of G with values from 1,...,k such that any path joining two vertices with the same label contains a vertex having a higher label. The tree-depth of G is the smallest value of k for which a k-ranking of G exists. The graph G is k-critical if it has tree-depth k and every proper minor of G has smaller tree-depth. As defined in [M. D. Barrus, J. Sinkovic, Uniqueness and minimal obstructions for tree-depth, Discrete Math 339 (2) (2015) 606-613], a graph G is 1-unique if for every vertex v in G, there exists an optimal ranking of G in which v is the unique vertex with label 1. In the above paper and [M. D. Barrus, J. Sinkovic, Classes of critical graphs for tree-depth, arXiv:1502.0577] the authors showed that several classes of critical graphs are 1-unique and asked whether all critical graphs have this property. We answer in the negative by demonstrating an infinite family of graphs which are critical but not 1-unique.

preprint2015arXiv

On the Principal Permanent Rank Characteristic Sequences of Graphs and Digraphs

The principal permanent rank characteristic sequence is a binary sequence $r_0 r_1 \ldots r_n$ where $r_k = 1$ if there exists a principal square submatrix of size $k$ with nonzero permanent and $r_k = 0$ otherwise, and $r_0 = 1$ if there is a zero diagonal entry. A characterization is provided for all principal permanent rank sequences obtainable by the family of nonnegative matrices as well as the family of nonnegative symmetric matrices. Constructions for all realizable sequences are provided. Results for skew-symmetric matrices are also included.

preprint2015arXiv

Uniqueness and minimal obstructions for tree-depth

A k-ranking of a graph G is a labeling of the vertices of G with values from {1,...,k} such that any path joining two vertices with the same label contains a vertex having a higher label. The tree-depth of G is the smallest value of k for which a k-ranking of G exists. The graph G is k-critical if it has tree-depth k and every proper minor of G has smaller tree-depth. We establish partial results in support of two conjectures about the order and maximum degree of k-critical graphs. As part of these results, we define a graph G to be 1-unique if for every vertex v in G, there exists an optimal ranking of G in which v is the unique vertex with label 1. We show that several classes of k-critical graphs are 1-unique, and we conjecture that the property holds for all k-critical graphs. Generalizing a previously known construction for trees, we exhibit an inductive construction that uses 1-unique k-critical graphs to generate large classes of critical graphs having a given tree-depth.

preprint2014arXiv

On the inertia set of a signed graph with loops

A signed graph is a pair $(G,Σ)$ , where $G=(V,E)$ is a graph (in which parallel edges and loops are permitted) with $V=\{1,\ldots,n\}$ and $Σ\subseteq E$ . The edges in $Σ$ are called odd edges and the other edges of $E$ even. By $S(G,Σ)$ we denote the set of all symmetric $n\times n$ real matrices $A=[a_{i,j}]$ such that if $a_{i,j} < 0$ , then there must be an even edge connecting $i$ and $j$ ; if $a_{i,j} > 0$ , then there must be an odd edge connecting $i$ and $j$ ; and if $a_{i,j} = 0$ , then either there must be an odd edge and an even edge connecting $i$ and $j$ , or there are no edges connecting $i$ and $j$ . (Here we allow $i=j$ .) For a symmetric real matrix $A$ , the partial inertia of $A$ is the pair $(p,q)$ , where $p$ and $q$ are the number of positive and negative eigenvalues of $A$ , respectively. If $(G,Σ)$ is a signed graph, we define the \emph{inertia set} of $(G,Σ)$ as the set of the partial inertias of all matrices $A \in S(G,Σ)$ . In this paper, we present a formula that allows us to obtain the minimal elements of the inertia set of $(G,Σ)$ in case $(G,Σ)$ has a $1$ -separation using the inertia sets of certain signed graphs associated to the $1$ -separation.

preprint2013arXiv

Minimum ranks of sign patterns via sign vectors and duality

A {\it sign pattern matrix} is a matrix whose entries are from the set $\{+,-, 0\}$ . The minimum rank of a sign pattern matrix $A$ is the minimum of the ranks of the real matrices whose entries have signs equal to the corresponding entries of $A$ . It is shown in this paper that for any $m \times n$ sign pattern $A$ with minimum rank $n-2$ , rational realization of the minimum rank is possible. This is done using a new approach involving sign vectors and duality. It is shown that for each integer $n\geq 9$ , there exists a nonnegative integer $m$ such that there exists an $n\times m$ sign pattern matrix with minimum rank $n-3$ for which rational realization is not possible. A characterization of $m\times n$ sign patterns $A$ with minimum rank $n-1$ is given (which solves an open problem in Brualdi et al. \cite{Bru10}), along with a more general description of sign patterns with minimum rank $r$ , in terms of sign vectors of certain subspaces. A number of results on the maximum and minimum numbers of sign vectors of $k$ -dimensional subspaces of $\mathbb R^n$ are obtained. In particular, it is shown that the maximum number of sign vectors of $2$ -dimensional subspaces of $\mathbb R^n$ is $4n+1$ . Several related open problems are stated along the way.

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.