One may generalize integer compositions by replacing positive integers with elements from an additive group, giving the broader concept of compositions over a group. In this note, we give some simple bijections between compositions over a finite group. It follows from these bijections that the number of compositions of a nonzero group element \( g \) is independent of \( g \). As a result, we derive a simple expression for the number of compositions of any given group element. This extends an earlier result for abelian groups which was obtained using generating functions and a multivariate multisection formula.

An acyclic ordering of a directed acyclic graph (DAG) \( G \) is a sequence \( \alpha \) of the vertices of \( G \) with the property that if \( i < j \), then there is a path in \( G \) from \( \alpha(i) \) to \( \alpha(j) \). In this paper, we explore the problem of finding the number of possible acyclic orderings of a general DAG. The main result is a method for reducing a general DAG to a simpler one when counting the number of acyclic orderings. Along the way, we develop a formula for quickly obtaining this count when a DAG is a tree.

The diagnosability of a multiprocessor system is one important study topic. In 2016, Zhang et al. proposed a new measure for fault diagnosis of the system, namely, the \( g \)-extra diagnosability, which restrains that every fault-free component has at least \( (g+1) \) fault-free nodes. As a favorable topology structure of interconnection networks, the \( n \)-dimensional alternating group graph \( AG_n \) has many good properties. In this paper, we prove that the 3-extra diagnosability of \( AG_n \) is \( 8n – 25 \) for \( n \geq 5 \) under the PMC model and for \( n \geq 7 \) MM* model.

M. Klešc et al. characterized graphs \( G_1 \) and \( G_2 \) for which the crossing number of their Cartesian product \( G_1 \square G_2 \) equals one or two. In this paper, their results are extended by giving the necessary and sufficient conditions for all pairs of graphs \( G_1 \) and \( G_2 \) for which the crossing number of their Cartesian product \( G_1 \square G_2 \) equals three, if one of the graphs \( G_1 \) and \( G_2 \) is a cycle.

In this paper we study relations between connected and weakly convex domination numbers. We show that in general the difference between these numbers can be arbitrarily large and we focus on the graphs for which a weakly convex domination number equals a connected domination number. We also study the influence of the edge removing on the weakly convex domination number, in particular we prove that the weakly convex domination number is an interpolating function.

Denote by \( p_m \) the \( m \)-th prime number (\( p_1 = 2 \), \( p_2 = 3 \), \( p_3 = 5 \), \( p_4 = 7 \), \dots). Let \( T \) be a rooted tree with branches \( T_1, T_2, \dots, T_r \). The Matula number \( M(T) \) of \( T \) is \( p_{M(T_1)} \cdot p_{M(T_2)} \cdots p_{M(T_r)} \), starting with \( M(K_1) = 1 \). This number was put forward half a century ago by the American mathematician David Matula. In this paper, we prove that the star (consisting of a root and leaves attached to it) and the binary caterpillar (a binary tree whose internal vertices form a path starting at the root) have the smallest and greatest Matula number, respectively, over all topological trees (rooted trees without vertices of outdegree 1) with a prescribed number of leaves – the extreme values are also derived.

Rotation distance between rooted binary trees is the minimum number of simple rotations needed to transform one tree into the other. Computing the rotation distance between a pair of rooted trees can be quickly reduced in cases where there is a common edge between the trees, or where a single rotation introduces a common edge. Tree pairs which do not have such a reduction are difficult tree pairs, where there is no generally known first step. Here, we describe efforts to count and estimate the number of such difficult tree pairs, and find that the fraction decreases exponentially fast toward zero. We also describe how knowing the number of distinct instances of the rotation distance problem is a helpful factor in making the computations more feasible.

In this paper, we characterize the set of spanning trees of \( G^1_{n,r} \) (a simple connected graph consisting of \( n \) edges, containing exactly one \textit{1-edge-connected chain} of \( r \) cycles \( C^1_r \) and \( G^1_{n,r} \), where \( C^1_r \) is a \textit{forest}). We compute the Hilbert series of the face ring \( k[\Delta_s(G^1_{n,r})] \) for the spanning simplicial complex \( \Delta_s(G^1_{n,r}) \). Also, we characterize associated primes of the facet ideal \( I_F(\Delta_s(G^1_{n,r})) \). Furthermore, we prove that the face ring \( k[\Delta_s(G^1_{n,r})] \) is Cohen-Macaulay.

Unlike undirected graphs where the concept of Roman domination has been studied very extensively over the past 15 years, Roman domination remains little studied in digraphs. However, the published works are quite varied and deal with different aspects of Roman domination, including for example, Roman bondage, Roman reinforcement, Roman dominating family of functions and the signed version of some Roman dominating functions. In this survey, we will explore some Roman domination related results on digraphs, some of which are extensions of well-known properties of the Roman domination parameters of undirected graphs.