An adjacent vertex distinguishing edge coloring, or an avd-coloring, of a simple graph \(G\) is a proper edge coloring of \(G\) such that for any two adjacent and distinct vertices \(u\) and \(v\) in \(G\), the set of colors assigned to the edges incident to \(u\) differs from the set of colors assigned to the edges incident to \(v\). In this paper, we prove that graphs with maximum degree \(3\) and with no isolated edges partly satisfy the adjacent vertex distinguishing edge coloring conjecture.

An \(L(2,1)\)-labeling of a graph \(G\) is a function \(f\) from the vertex set \(V(G)\) to the set of all nonnegative integers such that \(|f(x) – f(y)| \geq 2\) if \(d(x,y) = 1\) and \(|f(x) – f(y)| \geq 1\) if \(d(x,y) = 2\), where \(d(x,y)\) denotes the distance between vertices \(x\) and \(y\) in \(G\). The \(L(2,1)\)-labeling number \(\lambda(G)\) of \(G\) is the smallest number \(k\) such that \(G\) has an \(L(2,1)\)-labeling with \(\max\{f(v) : v \in V(G)\} = k\). We consider Cartesian sums of graphs and derive, both, lower and upper bounds for the \(L(2,1)\)-labeling number of this class of graphs; we use two approaches to derive the upper bounds for the \(L(2,1)\)-labeling number and both approaches improve previously known upper bounds. We also present several approximation algorithms for computing \(L(2,1)\)-labelings for Cartesian sum graphs.

Assume that \(G = (V, E)\) is an undirected graph with vertex set \(V\) and edge set \(E\). The ball \(B_r(v)\) denotes the vertices within graphical distance \(r\) from \(v\). A subset \(C \subseteq V\) is called an \(r\)-locating-dominating code if the sets \(I_r(v) = B_r(v) \cap C\) are distinct and non-empty for all \(v \in V \setminus C\). A code \(C\) is an \(r\)-identifying code if the sets \(I_r(v) = B_r(v) \cap C\) are distinct and non-empty for all vertices \(v \in V\). We study \(r\)-locating-dominating codes in the infinite king grid and, in particular, show that there is an \(r\)-locating-dominating code such that every \(r\)-identifying code has larger density. The infinite king grid is the graph with vertex set \(\mathbb{Z}^2\) and edge set \(\{(x_1, y_1), (x_2, y_2) \mid |x_1 – x_2| \leq 1, |y_1 – y_2| \leq 1, (x_1, y_1) \neq (x_2, y_2)\}\).

An antimagic labeling of a graph with \(n\) vertices and \(m\) edges is a bijection from the set of edges to the integers \(1, 2, \ldots, m\) such that all \(n\) vertex sums are pairwise distinct. For a cycle \(C_n\) of length \(n\), the \(k\)-th power of \(C_n\), denoted by \(C_n^k\), is the supergraph formed by adding an edge between all pairs of vertices of \(C_n\) with distance at most \(k\). Antimagic labelings for \(C_n^k\) are given where \(k = 2, 3, 4\).

In 1990, Kostochka and Sidorenko proposed studying the smallest number of list-colorings of a graph \(G\) among all assignments of lists of a given size \(n\) to its vertices. We say a graph \(G\) is \(n\)-monophilic if this number is minimized when identical \(n\)-color lists are assigned to all vertices of \(G\). Kostochka and Sidorenko observed that all chordal graphs are \(n\)-monophilic for all \(n\). Donner (1992) showed that every graph is \(n\)-monophilic for all sufficiently large \(n\). We prove that all cycles are \(n\)-monophilic for all \(n\); we give a complete characterization of \(2\)-monophilic graphs (which turns out to be similar to the characterization of \(2\)-choosable graphs given by Erdős, Rubin, and Taylor in 1980); and for every \(n\) we construct a graph that is \(n\)-choosable but not \(n\)-monophilic.

An adjacent vertex distinguishing total coloring of a graph \(G\) is a proper total coloring of \(G\) such that no two adjacent vertices are incident to the same set of colors. The minimum number of colors needed for such a coloring is denoted by \(\chi_{at}(G)\). In this note, we prove that \(\chi_{at}(G) = 5\) for some cubic graphs.

In this paper, a generalized notion of the fixed point property,namely the \(n\)-fixed point property, for posets is discussed. The \(n\)-fixed point property is proved to be equivalent to the fixed point property in lattices. Further, it is shown that a poset of finite width has the \(n\)-fixed point property for some natural number \(n\) if and only if every maximal chain in it is a complete lattice.

A graph is said to be equitably \(k\)-colorable if the vertex set \(V(G)\) can be partitioned into \(k\) independent subsets \(V_1, V_2, \ldots, V_k\) such that \(||V_i| – |V_j|| \leq 1\) (\(1 \leq i, j \leq k\)). A graph \(G\) is equitably \(k\)-choosable if, for any given \(k\)-uniform list assignment \(L\), \(G\) is \(L\)-colorable and each color appears on at most \(\lceil \frac{|V(G)|}{k} \rceil\) vertices. In this paper, we prove that if \(G\) is a graph such that \(\mathrm{mad}(G) \leq 3\), then \(G\) is equitably \(k\)-colorable and equitably \(k\)-choosable where \(k \geq \max\{\Delta(G), 5\}\).

For a vertex \(v\) of a graph \(G\), the unlabeled subgraph \(G-v\) is called a card of \(G\). We prove that the number of isolated vertices and the number of components of an \(n\)-vertex graph \(G\) can be determined from any collection of \(n-2\) of its cards for \(n \geq 10\). It is also proved that if two graphs of order \(n \geq 6\) have \(n-2\) cards in common, then the number of edges in them differs by at most one.

The Hosoya index \(z(G)\) of a graph \(G\) is defined as the total number of matchings of \(G\), and the Merrifield-Simmons index \(i(G)\) of a graph \(G\) is defined as the total number of independent sets of \(G\). Although there are many known results on these two indices, there exist few on a given class of graphs with perfect matchings. In this paper, we first introduce two new strengthened transformations. Then we characterize the extremal unicyclic graphs with perfect matching which have minimal, second minimal Hosoya index, and maximal, second maximal Merrifield-Simmons index, respectively.