Source author record

Michael D. Barrus

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

8works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Cliques in realization graphs

The realization graph $\mathcal{G}(d)$ of a degree sequence $d$ is the graph whose vertices are labeled realizations of $d$ , where edges join realizations that differ by swapping a single pair of edges. Barrus [On realization graphs of degree sequences, Discrete Mathematics, vol. 339 (2016), no. 8, pp. 2146-2152] characterized $d$ for which $\mathcal{G}(d)$ is triangle-free. Here, for any $n \geq 4$ , we describe a structure in realizations of $d$ that exactly determines whether $G(d)$ has a clique of size $n$ . As a consequence we determine the degree sequences $d$ for which $\mathcal{G}(d)$ is a complete graph on $n$ vertices.

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

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

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.

preprint2013arXiv

Hereditary unigraphs and Erdős--Gallai equalities

We give characterizations of the structure and degree sequences of hereditary unigraphs, those graphs for which every induced subgraph is the unique realization of its degree sequence. The class of hereditary unigraphs properly contains the threshold and matrogenic graphs, and the characterizations presented here naturally generalize those known for these other classes of graphs. The degree sequence characterization of hereditary unigraphs makes use of the list of values $k$ for which the $k$ th Erdős--Gallai inequality holds with equality for a graphic sequence. Using the canonical decomposition of Tyshkevich, we show how this list describes structure common among all realizations of an arbitrary graphic sequence.

preprint2013arXiv

Minimal forbidden sets for degree sequence characterizations

Given a set $\mathcal{F}$ of graphs, a graph $G$ is $\mathcal{F}$ -free if $G$ does not contain any member of $\mathcal{F}$ as an induced subgraph. Barrus, Kumbhat, and Hartke [M. D. Barrus, M. Kumbhat, and S. G. Hartke, Graph classes characterized both by forbidden subgraphs and degree sequences, J. Graph Theory (2008), no. 2, 131--148] called $\mathcal{F}$ a degree-sequence-forcing (DSF) set if, for each graph $G$ in the class $\mathcal{C}$ of $\mathcal{F}$ -free graphs, every realization of the degree sequence of $G$ is also in $\mathcal{C}$ . A DSF set is minimal if no proper subset is also DSF. In this paper, we present new properties of minimal DSF sets, including that every graph is in a minimal DSF set and that there are only finitely many DSF sets of cardinality $k$ . Using these properties and a computer search, we characterize the minimal DSF triples.

preprint2013arXiv

On fractional realizations of graph degree sequences

We introduce fractional realizations of a graph degree sequence and a closely associated convex polytope. Simple graph realizations correspond to a subset of the vertices of this polytope. We describe properties of the polytope vertices and characterize degree sequences for which each polytope vertex corresponds to a simple graph realization. These include the degree sequences of pseudo-split graphs, and we characterize their realizations both in terms of forbidden subgraphs and graph structure.

preprint2011arXiv

On 2-switches and isomorphism classes

A 2-switch is an edge addition/deletion operation that changes adjacencies in the graph while preserving the degree of each vertex. A well known result states that graphs with the same degree sequence may be changed into each other via sequences of 2-switches. We show that if a 2-switch changes the isomorphism class of a graph, then it must take place in one of four configurations. We also present a sufficient condition for a 2-switch to change the isomorphism class of a graph. As consequences, we give a new characterization of matrogenic graphs and determine the largest hereditary graph family whose members are all the unique realizations (up to isomorphism) of their respective degree sequences.

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.

Michael D. Barrus

Research overview

Is this your work?

8 publications

Cliques in realization graphs

Graphs with few trivial characteristic ideals

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

Uniqueness and minimal obstructions for tree-depth

Hereditary unigraphs and Erdős--Gallai equalities

Minimal forbidden sets for degree sequence characterizations

On fractional realizations of graph degree sequences

On 2-switches and isomorphism classes

See the researcher in context

Building this map preview