A graph labeling is an assignment of integers (labels) to the vertices and/or edges of a graph. Within vertex labelings, two main branches can be distinguished: difference vertex labelings that associate each edge of the graph with the difference of the labels of its endpoints. Graceful and edge-antimagic vertex labelings correspond to these branches, respectively. In this paper, we study some connections between them. Indeed, we study the conditions that allow us to transform any \(a\)-labeling (a special case of graceful labeling) of a tree into an \((a, 1)\)- and \((a, 2)\)-edge antimagic vertex labeling.

The domination number \(\gamma(G)\) of a graph \(G\) is the minimum cardinality among all dominating sets of \(G\), and the independence number \(\alpha(G)\) of \(G\) is the maximum cardinality among all independent sets of \(G\). For any graph \(G\), it is easy to see that \(\gamma(G) \leq \alpha(G)\). In this paper, we present a characterization of trees \(T\) with \(\gamma(T) = \alpha(T)\).

This paper generalizes the concept of locally connected graphs. A graph \(G\) is triangularly connected if for every pair of edges \(e_1, e_2 \in E(G)\), \(G\) has a sequence of \(3\)-cycles \(C_1, C_2, \ldots, C_l\) such that \(e_1 \in C_1, e_2 \in C_l\) and \(E(C_i) \cap E(C_{i+1}) \neq \emptyset\) for \(1 \leq i \leq l-1\). In this paper, we show that every triangularly connected \(K_{1,4}\)-free almost claw-free graph on at least three vertices is fully cycle extendable.

Let \(G = (V,E)\) be a simple graph. \({N}\) and \({Z}\) denote the set of all positive integers and the set of all integers, respectively. The sum graph \(G^+(S)\) of a finite subset \(S \subset{N}\) is the graph \((S, {E})\) with \(uv \in {E}\) if and only if \(u+v \in S\). \(G\) is a sum graph if it is isomorphic to the sum graph of some \(S \subseteq {N}\). The sum number \(\sigma(G)\) of \(G\) is the smallest number of isolated vertices, which result in a sum graph when added to \(G\). By extending \({N}\) to \({Z}\), the notions of the integral sum graph and the integral sum number of \(G\) are obtained, respectively. In this paper, we prove that \(\zeta(\overline{C_n}) = \sigma(\overline{C_n}) = 2n-7\) and that \(\zeta(\overline{W_n}) = \sigma(\overline{W_n}) = 2n-8\) for \(n \geq 7\).

We investigate the relationship between geodetic sets, \(k\)-geodetic sets, dominating sets, and independent sets in arbitrary graphs. As a consequence of the study, we provide several tight bounds on the geodetic number of a graph.

For \(1 \leq d \leq v-1\), let \(V\) denote the \(2v\)-dimensional symplectic space over a finite field \({F}_q\), and fix a \((v-d)\)-dimensional totally isotropic subspace \(W\) of \(V\). Let \({L}(d, 2v) = {P}\cup \{V\}\), where \({P} = \{A \mid A \text{ is a subspace of } V, A \cap W = \{0\} \text{ and } A \subset W^\perp\}\). Partially ordered by ordinary or reverse inclusion, two families of finite atomic lattices are obtained. This article discusses their geometricity, and computes their characteristic polynomials.

Let \(M\) be a graph, and let \(H(M)\) denote the homeomorphism class of \(M\), that is, the set of all graphs obtained from \(M\) by replacing every edge by a `chain’ of edges in series. Given \(M\) it is possible, either using the `chain polynomial’ introduced by E. G. Whitehead and myself (Discrete Math. \(204(1999) 337-356)\) or by ad hoc methods, to obtain an expression which subsumes the chromatic polynomials of all the graphs in \(H(M)\). It is a function of the number of colors and the lengths of the chains replacing the edges of \(M\). This function contains complete information about the chromatic properties of these graphs. In particular, it holds the answer to the question “Which pairs of graphs in \(H(M)\) are chromatically equivalent”. However, extracting this information is not an easy task.

In this paper, I present a method for answering this question. Although at first sight it appears to be wildly impractical, it can be persuaded to yield results for some small graphs. Specific results are given, as well as some general theorems. Among the latter is the theorem that, for any given integer \(\gamma\), almost all cyclically \(3\)-connected graphs with cyclomatic number \(\gamma\) are chromatically unique.

The analogous problem for the Tutte polynomial is also discussed, and some results are given.

Let \(G\) be a simple graph of order \(p \geq 2\). A proper \(k\)-total coloring of a simple graph \(G\) is called a \(k\)-vertex distinguishing proper total coloring (\(k\)-VDTC) if for any two distinct vertices \(u\) and \(v\) of \(G\), the set of colors assigned to \(u\) and its incident edges differs from the set of colors assigned to \(v\) and its incident edges. The notation \(\chi_{vt}(G)\) indicates the smallest number of colors required for which \(G\) admits a \(k\)-VDTC with \(k \geq \chi_{vt}(G)\). For every integer \(m \geq 3\), we will present a graph \(G\) of maximum degree \(m\) such that \(\chi_{vt}(G) < \chi_{vt}(H)\) for some proper subgraph \(H \subseteq G\).

Let \(G = (V,E)\) be a graph. Let \(\gamma(G)\) and \(\gamma_t(G)\) be the domination and total domination number of a graph \(G\), respectively. The \(\gamma\)-criticality and \(\gamma_t\)-criticality of Harary graphs are studied. The Question \(2\) of the paper [W. Goddard et al., The Diameter of total domination vertex critical graphs, Discrete Math. \(286 (2004), 255-261]\) is fully answered with the family of Harary graphs. It is answered to the second part of Question \(1\) of that paper with some Harary graphs.

Let \(G\) be a connected graph. The hyper-Wiener index \(WW(G)\) is defined as \(WW(G) = \frac{1}{2}\sum_{u,v \in V(G)} d(u,v) + \frac{1}{2} \sum_{u,v \in V(G)} d^2(u,v),\) with the summation going over all pairs of vertices in \(G\) and \(d(u,v)\) denotes the distance between \(u\) and \(v\) in \(G\). In this paper, we determine the upper or lower bounds on hyper-Wiener index of trees with given number of pendent vertices, matching number, independence number, domination number, diameter, radius, and maximum degree.