Given a directed graph, the Minimum Feedback Arc Set (FAS) problem asks for a minimum (size) set of arcs in a directed graph, which, when removed, results in an acyclic graph. In a seminal paper, Berger and Shor [1], in 1990, developed initial upper bounds for the FAS problem in general directed graphs. Here we find asymptotic lower bounds for the FAS problem in a class of random, oriented, directed graphs derived from the Erdős-Rényi model \(G(n,M)\), with n vertices and M (undirected) edges, the latter randomly chosen. Each edge is then randomly given a direction to form our directed graph. We show that \[Pr\left(\textbf{Y}^* \le M \left( \frac{1}{2} -\sqrt{\frac{\log n}{\Delta_{av}}}\right)\right),\] approaches zero exponentially in \(n\), with \(\textbf{Y}^*\) the (random) size of the minimum feedback arc set and \(\Delta_{av}=2M/n\) the average vertex degree. Lower bounds for random tournaments, a special case, were obtained by Spencer [13] and de la Vega [3] and these are discussed. In comparing the bound above to averaged experimental FAS data on related random graphs developed by K. Hanauer [8] we find that the approximation \(\textbf{Y}^*_{av} \approx M\left( \frac{1}{2} -\frac{1}{2}\sqrt{\frac{\log n}{\Delta_{av}}}\right)\) lies remarkably close graphically to the algorithmically computed average size \(\textbf{Y}^*_{av}\) of minimum feedback arc sets.

An alternative proof of A.B. Evans’ result on the existence of strong complete mappings on finite abelian groups is presented. Applications of strong complete mappings in computing the chromatic numbers of~certain Cayley graphs are discussed.

Let \(G = (V, E)\) be a simple graph. A subset \(D \subseteq V\) is called a dominating set of \(G\) if every vertex in \(V\) is either in \(D\) or has a neighbour in \(D\). A subset \(D \subseteq V\) is called an equitable dominating set of \(G\) if for every vertex \(v \in V \setminus D\), there exists a vertex \(u \in D\) such that \(uv \in E(G)\) and \(\lvert d_G(u) – d_G(v) \rvert \leq 1\). The minimum cardinality of an equitable dominating set of \(G\), denoted by \(\gamma^{e}(G)\), is called the equitable domination number of \(G\). In this paper, we study the equitable domination number of certain graph operators such as the double graph, the Mycielskian, and the subdivision of a graph.

This paper studies the Pell-Narayana sequence modulo \(m\). It starts by defining the Pell-Narayana numbers and examining their combinatorial relationships with well-known sequences and functions, including Eulerian, Catalan, and Delannoy numbers. Building on this, the concept of a Pell-Narayana orbit is introduced for a 2-generator group with generating pair \((x, y) \in G\), which allows the analysis of the periods of these orbits. The results include explicit calculations of the Pell-Narayana periods for polyhedral and binary polyhedral groups, depending on the choice of generating pair \((x, y)\), along with a discussion of their properties. Furthermore, the paper determines the periodic lengths of Pell-Narayana orbits for the groups \(Q_8, Q_8 \times \mathbb{Z}_{2m},\) and \(Q_8 \times_\varphi \mathbb{Z}_{2m}\) for all \(m \geq 3\).

A graph \(G=(V,E)\) is \(H\)-supermagic if there exists a bijection \(f\) from the set \(V\cup E\) to the set of integers \(\{1,2,3,\dots,|V|+|E|\}\), called \(H\)-supermagic labeling such that the sum of labels of all elements of every induced subgraph of \(G\) isomorphic to \(H\) is equal to the same integer and all vertex labels are in \(\{1,2,3,\dots,|V|\}\). We present a \((K_4-e)\)-supermagic labeling of the triangular ladder \(TL_{2n}\) for any \(n\geq2\).

Slilaty and Zaslavsky (2024) characterized all single-element extensions of graphic matroids in terms of a graphical structure called a cobiased graph. In this paper we characterize all orientations of a single-element extension of a graphic matroid in terms of graphically defined orientations of its associated cobiased graph. We also explain how these orientations can be canonically understood as dual to orientations of biased graphs if and only if the underlying graph is planar.

We consider a combinatorial question about searching for an unknown ideal \(\mu\) within a known pointed poset \(\lambda\). Elements of \(\lambda\) may be queried for membership in \(\mu\), but at most \(k\) positive queries are permitted. We provide a general search strategy for this problem, and establish new bounds (based on \(k\) and the degree and height of \(\lambda\)) for the total number of queries required to identify \(\mu\). We show that this strategy performs asymptotically optimally on the family of complete \(\ell\)-ary trees as the height grows.

Graph theory serves as a central and dynamic framework for the design and analysis of networks. Convex polytopes, as fundamental geometric entities, encompass a rich variety of mathematical structures and problems. The basic theory of convex polytopes involves the study of faces, normal cones, duality—particularly polarity—along with separation and other elementary concepts. A convex polytope can be described as a convex set of points within the \(n\)-dimensional Euclidean space \(\Re^{n}\). Among the various dimensions, the partition dimension is the most challenging, and determining its exact value is an NP-hard problem. In this work, we establish bounds for the partition dimension of convex polytopes \(T_\nu\), \(R_\nu\), and \(U_\nu\).

In \(1941\) Dushnik and Miller introduced the concept of dimension of a poset. In \(2020\) Bhavale and Waphare introduced the concept of an RC-lattice as a lattice in which all the reducible elements are lying on a chain. In this paper, we introduce the concept of a complete fundamental basic block and prove that its dimension is at the most three. Consequently, we prove that the dimension of an RC-lattice on \(n\) elements is at the most three. Further, we prove that an RC-lattice is non-planar if and only if its dimension is three.

For a graph, a smallest-last (SL) ordering is formed by iteratively deleting a vertex with smallest degree, then reversing the resulting list. The SL algorithm applies greedy coloring to a SL ordering. For a given vertex coloring algorithm, a graph is hard-to-color (HC) if every implementation of the algorithm results in a nonoptimal coloring. In 1997, Kubale et al. showed that \(C_{8}^{2}\) is the unique smallest HC graph for the SL algorithm. Extending this, we show that for \(k\geq4\), \(k+4\) is the smallest order of a HC graph for the SL algorithm with \(\chi\left(G\right)=k\). We also present a HC graph for the SL algorithm with \(\chi\left(G\right)=3\) that has order 10.