Gap vertex-distinguishing edge colorings of graphs

In this paper, we study a new coloring parameter of graphs called the gap vertex-distinguishing edge coloring. It consists in an edge-coloring of a graph $G$ which induces a vertex distinguishing labeling of $G$ such that the label of each vertex is given by the difference between the highest and the lowest colors of its adjacent edges. The minimum number of colors required for a gap vertex-distinguishing edge coloring of $G$ is called the gap chromatic number of $G$ and is denoted by $\mathrm{gap}\left(G\right)$.We here study the gap chromatic number for a large set of graphs $G$ of order $n$ and prove that $\mathrm{gap}\left(G\right)\in \{n?1,n,n+1\}$.     

Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

An interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors. A cyclic interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. Denote by $w\left(G\right)$ ($w_c\left(G\right)$) and $W\left(G\right)$ ($W_c\left(G\right)$) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$, respectively. We present some new sharp bounds on $w\left(G\right)$ and $W\left(G\right)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$-connected multigraph with an interval coloring, then $W\left(G\right)\le 1+?\frac{\left|V\left(G\right)\right|}{2}?(\Delta \left(G\right)?1)$. We also give several results towards the general conjecture that $W_c\left(G\right)\le \left|V\left(G\right)\right|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most $4$.     

Multi-set neighbor distinguishing 3-edge coloring

Let $G$ be a graph without isolated edges, and let $c:E\left(G\right)\to \{1,\dots ,k\}$ be a coloring of the edges, where adjacent edges may be colored the same. The color code of a vertex $v$ is the ordered $k$-tuple $(a_1,a_2,\dots ,a_k)$, where $a_i$ is the number of edges incident with $v$ that are colored $i$. If every two adjacent vertices of $G$ have different color codes, such a coloring is called multi-set neighbor distinguishing. In this paper, we prove that three colors are sufficient to produce a multi-set neighbor distinguishing edge coloring for every graph without isolated edges.     

A characterization of be-critical trees

The b-chromatic number of a graph G is the largest integer k such that G admits a proper coloring with k colors for which each color class contains a vertex that has at least one neighbor in all the other $k?1$ color classes. A graph G is called $b_e$-critical if the contraction of any edge e of G decreases the b-chromatic number of G. The purpose of this paper is the characterization of all $b_e$-critical trees.     

Doppelgangers and Lemke graphs

Let $G$ be a connected graph. A configuration of pebbles on $G$ is a function that assigns a nonnegative integer to each vertex. A pebbling move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if after making pebbling moves any vertex can get at least one pebble. The pebbling number of $G$, denoted $\pi \left(G\right)$, is the smallest integer such that any configuration of $\pi \left(G\right)$ pebbles on $G$ is solvable. A graph has the two-pebbling property if after placing more than $2\pi \left(G\right)?q$ pebbles on $G$, where $q$ is the number of vertices with pebbles, there is a sequence of pebbling moves so that at least two pebbles can be placed on any vertex. A graph without the two-pebbling property is called a Lemke graph. Previously, an infinite family of Lemke graphs was shown to exist by subdividing edges of the original Lemke graph. In this paper, we introduce a new way to create infinite families of Lemke graphs based on adding vertices as well as subdividing edges. We also characterize the configurations that violate the two-pebbling property on these graphs and conjecture another infinite family of Lemke graphs that generalizes the original Lemke graph.     

Domination in the hierarchical product and Vizing’s conjecture

Given a graph $G$, a set $S?V\left(G\right)$ is a dominating set of $G$ if every vertex of $G$ is either in $S$ or adjacent to a vertex in $S$. The domination number of $G$, denoted $\gamma \left(G\right)$, is the minimum cardinality of a dominating set of $G$. Vizing’s conjecture states that $\gamma (G\square H)\ge \gamma \left(G\right)\gamma \left(H\right)$ for any graphs $G$ and $H$ where $G\square H$ denotes the Cartesian product of $G$ and $H$. In this paper, we continue the work by Anderson et al. (2016) by studying the domination number of the hierarchical product. Specifically, we show that partitioning the vertex set of a graph in a particular way shows a trend in the lower bound of the domination number of the product, providing further evidence that the conjecture is true.     

b-coloring of Kneser graphs

A $b$-coloring of a graph $G$ with $k$ colors is a proper coloring of $G$ using $k$ colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer $k$ for which $G$ has a $b$-coloring using $k$ colors is the $b$-chromatic number $b\left(G\right)$ of $G$. The $b$-spectrum $S_b\left(G\right)$ of a graph $G$ is the set of positive integers $k,\chi \left(G\right)\le k\le b\left(G\right)$, for which $G$ has a $b$-coloring using $k$ colors. A graph $G$ is $b$-continuous if $S_b\left(G\right)$ = the closed interval $[\chi \left(G\right),b\left(G\right)]$. In this paper, we obtain an upper bound for the $b$-chromatic number of some families of Kneser graphs. In addition we establish that $[\chi \left(G\right),n+k+1]?S_b\left(G\right)$ for the Kneser graph $G=K(2n+k,n)$ whenever $3\le n\le k+1$. We also establish the $b$-continuity of some families of regular graphs which include the family of odd graphs.     

Indicated coloring of graphs

We study a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $G$ (regardless of Ben’s strategy) is called the indicated chromatic number of $G$, and denoted by ${\chi }_i\left(G\right)$. We approach the question how much ${\chi }_i\left(G\right)$ differs from the usual chromatic number $\chi \left(G\right)$. In particular, whether there is a function $f$ such that ${\chi }_i\left(G\right)?f\left(\chi \left(G\right)\right)$ for every graph $G$. We prove that $f$ cannot be linear with leading coefficient less than $4/3$. On the other hand, we show that the indicated chromatic number of random graphs is bounded roughly by $4\chi \left(G\right)$. We also exhibit several classes of graphs for which ${\chi }_i\left(G\right)=\chi \left(G\right)$ and show that this equality for any class of perfect graphs implies Clique-Pair Conjecture for this class of graphs.     

On the independence number of the power graph of a finite group

The power graph ${\Gamma }_G$ of a finite group $G$ is the graph whose vertex set is $G$, two distinct elements being adjacent if one is a power of the other. In this paper, we give sharp lower and upper bounds for the independence number of ${\Gamma }_G$ and characterize the groups achieving the bounds. Moreover, we determine the independence number of ${\Gamma }_G$ if $G$ is cyclic, dihedral or generalized quaternion. Finally, we classify all finite groups $G$ whose power graphs have independence number 3 or $n?2$, where $n$ is the order of $G$.     

Vertex and edge spread of zero forcing number,maximum nullity,and minimum rank of a graph

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for $i\ne j$) is nonzero whenever $\{i\text{,}j\}$ is an edge in G and is zero otherwise; maximum nullity is taken over the same set of matrices. The zero forcing number is the minimum size of a zero forcing set of vertices and bounds the maximum nullity from above. The spread of a graph parameter at a vertex v or edge e of G is the difference between the value of the parameter on G and on $G-v$ or $G-e$. Rank spread (at a vertex) was introduced in [4]. This paper introduces vertex spread of the zero forcing number and edge spreads for minimum rank/maximum nullity and zero forcing number. Properties of the spreads are established and used to determine values of the minimum rank/maximum nullity and zero forcing number for various types of grids with a vertex or edge deleted.     

A note on the list vertex arboricity of toroidal graphs

The vertex arboricity $a\left(G\right)$ of a graph $G$ is the minimum number of colors required to color the vertices of $G$ such that no cycle is monochromatic. The list vertex arboricity $a_l\left(G\right)$ is the list-coloring version of this concept. In this note, we prove that if $G$ is a toroidal graph, then $a_l\left(G\right)\le 4$; and $a_l\left(G\right)=4$ if and only if $G$ contains $K_7$ as an induced subgraph.     

Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems

A transition in a graph is defined as a pair of adjacent edges. A transition system of an Eulerian graph refers to a set of partitions such that for each vertex of the graph, there corresponds to a partition of the set of edges incident to the vertex into transitions. A generalized transition system $F\left(G\right)$ over a graph $G$ defines a set of transitions over $G$. A compatible Eulerian circuit of an Eulerian graph $G$ with a generalized transition system $F\left(G\right)$ is defined as an Eulerian circuit in which no two consecutive edges form a transition defined by $F\left(G\right)$. In this paper, we further introduce the concept of weakly generalized transition system which is an extension of the generalized transition system and prove some Ore-type sufficient conditions for the existence of compatible Eulerian circuits in Eulerian graphs with (weakly) generalized transition systems and obtain corresponding results for Eulerian digraphs. Our conditions improve some previous results due to Jackson and Isaak, respectively.     

Generalizations of Graham’s pebbling conjecture

We investigate generalizations of pebbling numbers and of Graham’s pebbling conjecture that $\pi \left(G\square H\right)\le \pi \left(G\right)\pi \left(H\right)$, where $\pi \left(G\right)$ is the pebbling number of the graph $G$. We develop new machinery to attack the conjecture, which is now twenty years old. We show that certain conjectures imply others that initially appear stronger. We also find counterexamples that shows that Sjöstrand’s theorem on cover pebbling does not apply if we allow the cost of transferring a pebble from one vertex to an adjacent vertex to depend on the weight of the edge and we describe an alternate pebbling number for which Graham’s conjecture is demonstrably false.     

Total domination in inflated graphs

The inflation $G_I$ of a graph $G$ is obtained from $G$ by replacing every vertex $x$ of degree $d\left(x\right)$ by a clique $X=K_{d\left(x\right)}$ and each edge $xy$ by an edge between two vertices of the corresponding cliques $X$ and $Y$ of $G_I$ in such a way that the edges of $G_I$ which come from the edges of $G$ form a matching of $G_I$. A set $S$ of vertices in a graph $G$ is a total dominating set, abbreviated TDS, of $G$ if every vertex of $G$ is adjacent to a vertex in $S$. The minimum cardinality of a TDS of $G$ is the total domination number ${\gamma }_t\left(G\right)$ of $G$. In this paper, we investigate total domination in inflated graphs. We provide an upper bound on the total domination number of an inflated graph in terms of its order and matching number. We show that if $G$ is a connected graph of order $n\ge 2$, then ${\gamma }_t\left(G_I\right)\ge 2n/3$, and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of $G$ to be at least $2$, then we show that ${\gamma }_t\left(G_I\right)\ge n$, with equality if and only if $G$ has a perfect matching. If we increase the minimum degree requirement of $G$ to be at least $3$, then we show ${\gamma }_t\left(G_I\right)\ge n$, with equality if and only if every minimum TDS of $G_I$ is a perfect total dominating set of $G_I$, where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set.