Source author record

Sarah Loeb

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

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Determining Number and Cost of Generalized Mycielskian Graphs

A set $S$ of vertices is a determining set for a graph $G$ if every automorphism of $G$ is uniquely determined by its action on $S$ . The size of a smallest determining set for $G$ is called its determining number, $Det(G)$ . A graph $G$ is said to be $d$ -distinguishable if there is a coloring of the vertices with $d$ colors so that only the trivial automorphism preserves the color classes. The smallest such $d$ is the distinguishing number, $Dist(G)$ . If $Dist(G) = 2$ , the cost of 2-distinguishing, $ρ(G)$ , is the size of a smallest color class over all 2-distinguishing colorings of $G$ . The Mycielskian, $μ(G)$ , of a graph $G$ is constructed by adding a shadow master vertex $w$ , and for each vertex $v_i$ of $G$ adding a shadow vertex $u_i$ with edges so that the neighborhood of $u_i$ in $μ(G)$ is the same as the neighborhood of $v_i$ in $G$ with the addition of $w$ . That is, $N(u_i)=N_G(v_i)\cup\{w\}$ . The generalized Mycielskian $μ^{(t)}(G)$ of a graph $G$ is a Mycielskian graph with $t$ layers of shadow vertices, each with edges to layers above and below, and $w$ only adjacent to the top layer of shadow vertices. A graph is twin-free if it has no pair of vertices with the same set of neighbors. This paper examines the determining number and, when relevant, the cost of 2-distinguishing for Mycielskians and generalized Mycielskians of simple graphs with no isolated vertices. In particular, if $G \neq K_2$ is twin-free with no isolated vertices, then $Det(μ^{(t)}(G)) = Det(G)$ . Further, if $Det(G) = k \geq 2$ and $t \ge k-1$ , then $Dist(μ^{(t)}(G))=2$ , and $Det(μ^{(t)}(G)) = ρ(μ^{(t)}(G))= k$ . For $G$ with twins, we develop a framework using quotient graphs with respect to equivalence classes of twin vertices to give bounds on the determining number of Mycielskians. Moreover, we identify classes of graphs with twins for which $Det(μ^{(t)}(G)) = (t{+}1) Det(G)$ .

preprint2021arXiv

Distinguishing Generalized Mycielskian Graphs

A graph $G$ is $d$ -distinguishable if there is a coloring of the vertices with $d$ colors so that only the trivial automorphism preserves the color classes. The smallest such $d$ is the distinguishing number, $\operatorname{Dist}(G)$ . The Mycielskian $μ(G)$ of a graph $G$ is constructed by adding a shadow vertex $u_i$ for each vertex $v_i$ of $G$ and one additional vertex $w$ and adding edges so that $N(u_i)~=~N_G(v_i)~\cup~\{w\}$ . The generalized Mycielskian $μ_t(G)$ is a Mycielskian graph with $t$ layers of shadow vertices, each with edges to layers above and below. This paper examines the distinguishing number of the traditional and generalized Mycielskian graphs. Notably, if $G~\neq ~K_1,~K_2$ and the number of isolated vertices in $μ_t(G)$ is at most $\operatorname{Dist}(G)$ , then $\operatorname{Dist}(μ_t(G)) \le \operatorname{Dist}(G)$ . This result proves and exceeds a conjecture of Alikhani and Soltani.

preprint2021arXiv

Symmetry Parameters for Mycielskian Graphs

The Mycielskian construction, denoted $μ(G)$ , takes a finite simple graph $G$ to a larger graph with of the same clique number but larger chromatic number. The generalized Mycielskian construction, denoted $μ_t(G)$ , takes $G$ to a larger graph with the same chromatic number but with larger odd girth. In this chapter we look at symmetry parameters of $μ(G)$ and $μ_t(G)$ in terms of the same parameters of $G$ . These symmetry parameters include determining number, distinguishing number, and cost of distinguishing.

preprint2016arXiv

Asymptotically optimal neighbor sum distinguishing total colorings of graphs

Given a proper total $k$ -coloring $c:V(G)\cup E(G)\to\{1,2,\ldots,k\}$ of a graph $G$ , we define the value of a vertex $v$ to be $c(v) + \sum_{uv \in E(G)} c(uv)$ . The smallest integer $k$ such that $G$ has a proper total $k$ -coloring whose values form a proper coloring is the neighbor sum distinguishing total chromatic number of $G$ , $χ"_Σ(G)$ . Pilśniak and Woźniak (2013) conjectured that $χ"_Σ(G)\leq Δ(G)+3$ for any simple graph with maximum degree $Δ(G)$ . In this paper, we prove this bound to be asymptotically correct by showing that $χ"_Σ(G)\leq Δ(G)(1+o(1))$ . The main idea of our argument relies on Przybyło's proof (2014) regarding neighbor sum distinguishing edge-colorings.

preprint2015arXiv

Dynamic coloring parameters for graphs with given genus

A proper vertex coloring of a graph $G$ is $r$ -dynamic if for each $v\in V(G)$ , at least $\min\{r,d(v)\}$ colors appear in $N_G(v)$ . In this paper we investigate $r$ -dynamic versions of coloring, list coloring, and paintability. We prove that planar and toroidal graphs are 3-dynamically 10-colorable, and this bound is sharp for toroidal graphs. We also give bounds on the minimum number of colors needed for any $r$ in terms of the genus of the graph: for sufficiently large $r$ , every graph with genus $g$ is $r$ -dynamically $((r+1)(g+5)+3)$ -colorable when $g\leq2$ and $r$ -dynamically $((r+1)(2g+2)+3)$ -colorable when $g\geq3$ . Furthermore, each of these upper bounds for $r$ -dynamic $k$ -colorability also holds for $r$ -dynamic $k$ -choosability and for $r$ -dynamic $k$ -paintability. We develop a method to prove that certain configurations are reducible for each of the corresponding $r$ -dynamic parameters.

preprint2015arXiv

I,F-partitions of Sparse Graphs

A star $k$ -coloring is a proper $k$ -coloring where the union of two color classes induces a star forest. While every planar graph is 4-colorable, not every planar graph is star 4-colorable. One method to produce a star 4-coloring is to partition the vertex set into a 2-independent set and a forest; such a partition is called an I,F-partition. We use a combination of potential functions and discharging to prove that every graph with maximum average degree less than $\frac{5}{2}$ has an I,F-partition, which is sharp and answers a question of Cranston and West [A guide to the discharging method, arXiv:1306.4434]. This result implies that planar graphs of girth at least 10 are star 4-colorable, improving upon previous results of Bu, Cranston, Montassier, Raspaud, and Wang [Star coloring of sparse graphs, J. Graph Theory 62 (2009), 201-219].

preprint2014arXiv

Fool's Solitaire on Joins and Cartesian Products of Graphs

Peg solitaire is a game generalized to connected graphs by Beeler and Hoilman. In the game pegs are placed on all but one vertex. If $xyz$ form a 3-vertex path and $x$ and $y$ each have a peg but $z$ does not, then we can remove the pegs at $x$ and $y$ and place a peg at $z$ . By analogy with the moves in the original game, this is called a jump. The goal of the peg solitaire game on graphs is to find jumps that reduce the number of pegs on the graph to 1. Beeler and Rodriguez proposed a variant where we instead want to maximize the number of pegs remaining when no more jumps can be made. Maximizing over all initial locations of a single hole, the maximum number of pegs left on a graph $G$ when no jumps remain is the fool's solitaire number $F(G)$ . We determine the fool's solitaire number for the join of any graphs $G$ and $H$ . For the cartesian product, we determine $F(G \Box K_k)$ when $k \ge 3$ and $G$ is connected and show why our argument fails when $k=2$ . Finally, we give conditions on graphs $G$ and $H$ that imply $F(G \Box H) \ge F(G) F(H)$ .

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.

Sarah Loeb

Research overview

Is this your work?

7 publications

Determining Number and Cost of Generalized Mycielskian Graphs

Distinguishing Generalized Mycielskian Graphs

Symmetry Parameters for Mycielskian Graphs

Asymptotically optimal neighbor sum distinguishing total colorings of graphs

Dynamic coloring parameters for graphs with given genus

I,F-partitions of Sparse Graphs

Fool's Solitaire on Joins and Cartesian Products of Graphs

See the researcher in context

Building this map preview