Source author record

Kirsti Wash

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

ResearcherUnclaimed source record

math.CO nlin.AO

Catalog footprint

Research overview

8works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On minimum identifying codes in some Cartesian product graphs

An identifying code in a graph is a dominating set that also has the property that the closed neighborhood of each vertex in the graph has a distinct intersection with the set. The minimum cardinality of an identifying code, or ID code, in a graph $G$ is called the ID code number of $G$ and is denoted $\gid(G)$. In this paper, we give upper and lower bounds for the ID code number of the prism of a graph, or $G\Box K_2$ . In particular, we show that $\gid(G \Box K_2) \ge \gid(G)$ and we show that this bound is sharp. We also give upper and lower bounds for the ID code number of grid graphs and a general upper bound for $\gid(G\Box K_2)$.

preprint2016arXiv

Packing chromatic number under local changes in a graph

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ such that there exists a $k$ -vertex coloring of $G$ in which any two vertices receiving color $i$ are at distance at least $i+1$ . It is proved that in the class of subcubic graphs the packing chromatic number is bigger than $13$ , thus answering an open problem from [Gastineau, Togni, $S$ -packing colorings of cubic graphs, Discrete Math.\ 339 (2016) 2461--2470]. In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if $S_e(G)$ is the graph obtained from a graph $G$ by subdividing its edge $e$ , then $\left\lfloor χ_ρ(G)/2 \right\rfloor +1 \le χ_ρ(S_e(G)) \le χ_ρ(G)+1$ .

preprint2016arXiv

Packing chromatic number, $(1,1,2,2)$ -colorings, and characterizing the Petersen graph

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $Π_1,\ldots,Π_k$ , where $Π_i$ , $i\in [k]$ , is an $i$ -packing. The following conjecture is posed and studied: if $G$ is a subcubic graph, then $χ_ρ(S(G))\le 5$ , where $S(G)$ is the subdivision of $G$ . The conjecture is proved for all generalized prisms of cycles. To get this result it is proved that if $G$ is a generalized prism of a cycle, then $G$ is $(1,1,2,2)$ -colorable if and only if $G$ is not the Petersen graph. The validity of the conjecture is further proved for graphs that can be obtained from generalized prisms in such a way that one of the two $n$ -cycles in the edge set of a generalized prism is replaced by a union of cycles among which at most one is a 5-cycle. The packing chromatic number of graphs obtained by subdividing each of its edges a fixed number of times is also considered.

preprint2016arXiv

Spectral properties of the hierarchical product of graphs

The hierarchical product of two graphs represents a natural way to build a larger graph out of two smaller graphs with less regular and therefore more heterogeneous structure than the Cartesian product. Here we study the eigenvalue spectrum of the adjacency matrix of the hierarchical product of two graphs. Introducing a coupling parameter describing the relative contribution of each of the two smaller graphs, we perform an asymptotic analysis for the full spectrum of eigenvalues of the adjacency matrix of the hierarchical product. Specifically, we derive the exact limit points for each eigenvalue in the limits of small and large coupling, as well as the leading-order relaxation to these values in terms of the eigenvalues and eigenvectors of the two smaller graphs. Given its central roll in the structural and dynamical properties of networks, we study in detail the Perron-Frobenius, or largest, eigenvalue. Finally, as an example application we use our theory to predict the epidemic threshold of the Susceptible-Infected-Susceptible model on a hierarchical product of two graphs.

preprint2015arXiv

Matchings and Path Covers with applications to Domination in Graphs

Let $G$ be a graph with no isolated vertex. A matching in $G$ is a set of edges that are pairwise not adjacent in $G$ , while the matching number, $α'(G)$ , of $G$ is the maximum size of a matching in $G$ . The path covering number, $\rm{pc}(G)$ , of $G$ is the minimum number of vertex disjoint paths such that every vertex belongs to a path in the cover. We show that if $G$ has order $n$ , then $α'(G) + \frac{1}{2}\rm{pc}(G) \ge \frac{n}{2}$ and we provide a constructive characterization of the graphs achieving equality in this bound. It is known that $γ(G) \le α'(G)$ and $γ_t(G) \le α'(G) + \rm{pc}(G)$ , where $γ(G)$ and $γ_t(G)$ denote the domination and the total domination number of $G$ . As an application of our result on the matching and path cover numbers, we show that if $G$ is a graph with $δ(G) \ge 3$ , then $γ_t(G) \le α'(G) + \frac{1}{2}(\rm{pc}(G) - 1)$ , and this bound is tight. A set $S$ of vertices in $G$ is a neighborhood total dominating set of $G$ if it is a dominating set of $G$ with the property that the subgraph induced by the open neighborhood of the set $S$ has no isolated vertex. The neighborhood total domination number, $γ_{\rm nt}(G)$ , is the minimum cardinality of a neighborhood total dominating set of $G$ . We observe that $γ(G) \le γ_{\rm nt}(G) \le γ_t(G)$ . As a further application of our result on the matching and path cover numbers, we show that if $G$ is a connected graph on at least six vertices, then $γ_{\rm nt}(G) \le α'(G) + \frac{1}{2}\rm{pc}(G)$ and this bound is tight.

preprint2014arXiv

Trees with Large Neighborhood Total Domination Number

In this paper, we continue the study of neighborhood total domination in graphs first studied by Arumugam and Sivagnanam [Opuscula Math. 31 (2011), 519--531]. A neighborhood total dominating set, abbreviated NTD-set, in a graph $G$ is a dominating set $S$ in $G$ with the property that the subgraph induced by the open neighborhood of the set $S$ has no isolated vertex. The neighborhood total domination number, denoted by $\gnt(G)$, is the minimum cardinality of a NTD-set of $G$ . Every total dominating set is a NTD-set, implying that $γ(G) \le \gnt(G) \le \gt(G)$, where $γ(G)$ and $\gt(G)$ denote the domination and total domination numbers of $G$ , respectively. Arumugam and Sivagnanam posed the problem of characterizing the connected graphs $G$ of order $n \ge 3$ achieving the largest possible neighborhood total domination number, namely $\gnt(G) = \lceil n/2 \rceil$. A partial solution to this problem was presented by Henning and Rad [Discrete Applied Mathematics 161 (2013), 2460--2466] who showed that $5$ -cycles and subdivided stars are the only such graphs achieving equality in the bound when $n$ is odd. In this paper, we characterize the extremal trees achieving equality in the bound when $n$ is even. As a consequence of this tree characterization, a characterization of the connected graphs achieving equality in the bound when $n$ is even can be obtained noting that every spanning tree of such a graph belongs to our family of extremal trees.

preprint2013arXiv

Edgeless graphs are the only universal fixers

Given two disjoint copies of a graph $G$ , denoted $G^1$ and $G^2$ , and a permutation $π$ of $V(G)$ , the graph $πG$ is constructed by joining $u \in V(G^1)$ to $π(u) \in V(G^2)$ for all $u \in V(G^1)$ . $G$ is said to be a universal fixer if the domination number of $πG$ is equal to the domination number of $G$ for all $π$ of $V(G)$ . In 1999 it was conjectured that the only universal fixers are the edgeless graphs. Since then, a few partial results have been shown. In this paper, we prove the conjecture completely.

preprint2012arXiv

Identifying codes of the direct product of two cliques

An identifying code in a graph is a dominating set that also has the property that the closed neighborhood of each vertex in the graph has a distinct intersection with the set. It was recently shown by Gravier, Moncel and Semri that the minimum cardinality of an identifying code for the Cartesian product of two cliques of the same order n is the floor of 3n/2. We consider identifying codes of the direct product of two cliques. In particular, we answer a question of Klavzar and determine the minimum cardinality of an identifying code for the direct product of any two cliques.

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.

Kirsti Wash

Research overview

Is this your work?

8 publications

On minimum identifying codes in some Cartesian product graphs

Packing chromatic number under local changes in a graph

Packing chromatic number, $(1,1,2,2)$ -colorings, and characterizing the Petersen graph

Spectral properties of the hierarchical product of graphs

Matchings and Path Covers with applications to Domination in Graphs

Trees with Large Neighborhood Total Domination Number

Edgeless graphs are the only universal fixers

Identifying codes of the direct product of two cliques

See the researcher in context

Building this map preview

Kirsti Wash

Research overview

Is this your work?

8 publications

On minimum identifying codes in some Cartesian product graphs

Packing chromatic number under local changes in a graph

Packing chromatic number, (1,1,2,2)(1,1,2,2)(1,1,2,2)-colorings, and characterizing the Petersen graph

Spectral properties of the hierarchical product of graphs

Matchings and Path Covers with applications to Domination in Graphs

Trees with Large Neighborhood Total Domination Number

Edgeless graphs are the only universal fixers

Identifying codes of the direct product of two cliques

See the researcher in context

Building this map preview

Packing chromatic number, $(1,1,2,2)$ -colorings, and characterizing the Petersen graph