This paper deals with a new kind of graph labeling similar to the well known harmonious, graceful, and elegant labelings. A polychrome labeling of a simple and connected graph \(G = (V, E)\) by an abelian group \(A\) is a bijective map from \(V\) onto \(A\) such that the induced edge labeling \(f^*(uv) = f(v) + f(w), uv \in E\), is injective. Polychrome labelings of a path and a cycle by a large class of abelian groups are designed, and the connection to the above mentioned labelings is shown. In addition, the author presents a conjecture which is similar to a famous conjecture of G. Ringel about graceful trees (see {[9]}).

A graph is well-covered if it has no isolated vertices and all the maximal independent sets have the same cardinality. If furthermore this cardinality is exactly half the number of vertices, the graph is called very well covered. Sankaranarayana in \({[5]}\) presented a certain subclass of well covered graphs (called Wan) and gave a characterization of this class which generalized the characterization of very well covered graphs given by Favaron \([2]\) . The purpose of this article is to generalize to this new subclass some results concerning the stability, domination, and irredundance parameters proved for very well covered graphs in \([2]\) .

Three new characterizations of matroids are presented.

A decomposition of a graph \(H\) is a family of subgraphs of \(H\) such that each edge of \(H\) is contained in exactly one member of the family. For a graph \(G\), a \(G\)-decomposition of the graph \(H\) is a decomposition of \(H\) into subgraphs isomorphic to \(G\). If \(H\) has a \(G\)-decomposition, \(H\) is said to be \(G\)-decomposable; this is denoted by \(H \rightarrow G\). In this paper, we prove by construction that the complete graph \(K_{24}\) is \(G\)-decomposable, where \(G\) is the complementary graph of the path \(P_5\).

A unified approach to prove former connectivity results of Tutte, Cunningham, Inukai, and Weinberg, Oxley, and Wagner.

This paper deals with the existence of \({Z}\)-cyclic Room squares of order \(2v\) (or of side \(2v-1\)) whenever \(2v-1 =\Pi_{i=1}^{n}p^{\alpha_i}\), ( \(p_i=2^{m_i}b_i+1\geq 7\) are distinct primes, \(b_i\) are odd, \(b_i > 1\), and \(\alpha_i\) are positive integers, \(i = 1, 2, \ldots, n\)), and includes some further results involving Fermat primes.

Let \(G\) be a connected \((p,q)\)-graph. Let \(\gamma_c\) denote the connected domination number of \(G\). In this paper, we prove that \(q\leq \lfloor\frac{p(p-\gamma_c)}{2}\rfloor\) and equality holds if and only if \(G = C_p\) or \(K_p\) or \(K_p – Q\) where \(Q\) is a minimum edge cover of \(K_p\). We obtain similar bounds on \(\gamma_q\) for graphs with given: Total domination number \(\gamma_t\) Clique domination number \(\gamma_k\) Edge domination number \(\gamma ‘\) Connected edge domination number \(\gamma’_{c }\) and for each of these parameters, characterize the class of graphs attaining the corresponding bound.

We consider all \(2-(v,3)\) trades in which every pair appears at most once in each part of the trade, and we call them Steiner Triple Trades \({STT}(v)\). We completely classify \({STT}(v)\) with \(6 \leq vol(T) \leq 9\).

Let \(G\) be a graph. A function \(f: V(G) \to \{1, 2, \ldots, k\}\) is a \(k\)-ranking for \(G\) if \(f(u) = f(v)\) implies that every \(u-v\) path \(P\) contains a vertex \(w\) such that \(f(w) > f(u)\). A function \(f: V(G) \to \{1, 2, \ldots, 4\}\) is a minimal \(k\)-ranking if \(f\) is a \(k\)-ranking and for any \(x\) such that \(f(x) > 1\) the function \(g(z) = f(z)\) for \(z \neq x\) and \(1 \leq g(x) < f(x)\) is not a \(k\)-ranking. This paper establishes further properties of minimal rankings, gives a procedure for constructing minimal rankings, and determines, for some classes of graphs, the minimum value and maximum value of \(k\) for which \(G\) has a minimal \(k\)-ranking. In addition, we establish tighter bounds for the minimum value of \(k\) for which \(G\) has a \(k\)-ranking.

A tournament is a complete directed graph. A convex subset is a vertex subset with the property that every two-path beginning and ending inside the convex subset is contained completely within the subset. This paper shows a relationship between convex subsets and transitive closures which leads to an optimal \(O(n^3)\)-time algorithm for finding all convex subsets in a tournament.