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.

Cut vertices are often used as a measure of nodes’ importance within a network. These are nodes whose failure disconnects a connected graph. Let \(N(G)\) be the number of connected induced subgraphs of a graph \(G\). In this work, we investigate the maximum of \(N(G)\) where \(G\) is a unicyclic graph with \(n\) nodes of which \(c\) are cut vertices. For all valid \(n,c\), we give a full description of those maximal (that maximise \(N(.)\)) unicyclic graphs. It is found that there are generally two maximal unicyclic graphs. For infinitely many values of \(n,c\), however, there is a unique maximal unicyclic graph with \(n\) nodes and \(c\) cut vertices. In particular, the well-known negative correlation between the number of connected induced subgraphs of trees and the Wiener index (sum of distances) fails for unicyclic graphs with \(n\) nodes and \(c\) cut vertices: for instance, the maximal unicyclic graph with \(n=3,4\mod 5\) nodes and \(c=n-5>3\) cut vertices is different from the unique graph that was shown by Tan et al. [The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices. J. Appl. Math. Comput., 55:1–24, 2017] to minimise the Wiener index. Our main characterisation of maximal unicyclic graphs with respect to the number of connected induced subgraphs also applies to unicyclic graphs with \(n\) nodes, \(c\) cut vertices and girth at most \(g>3\), since it is shown that the girth of every maximal graph with \(n\) nodes and \(c\) cut vertices cannot exceed \(4\).

The honeymoon Oberwolfach problem HOP\((2m_1,2m_2,\ldots,2m_t)\) asks the following question. Given \(n=m_1+m_2+\ldots +m_t\) newlywed couples at a conference and \(t\) round tables of sizes \(2m_1,2m_2,\ldots,2m_t\), is it possible to arrange the \(2n\) participants at these tables for \(2n-2\) meals so that each participant sits next to their spouse at every meal, and sits next to every other participant exactly once? A solution to HOP\((2m_1,2m_2,\ldots,2m_t)\) is a decomposition of \(K_{2n}+(2n-3)I\), the complete graph \(K_{2n}\) with \(2n-3\) additional copies of a fixed 1-factor \(I\), into 2-factors, each consisting of disjoint \(I\)-alternating cycles of lengths \(2m_1,2m_2,\ldots,2m_t\). The honeymoon Oberwolfach problem was introduced in a 2019 paper by Lepine and Šajna. The authors conjectured that HOP\((2m_1,2m_2,\ldots,\) \(2m_t)\) has a solution whenever the obvious necessary conditions are satisfied, and proved the conjecture for several large cases, including the uniform cycle length case \(m_1=\ldots=m_t\), and the small cases with \(n \le 9\). In the present paper, we extend the latter result to all cases with \(n \le 20\) using a computer-assisted search.

We introduce and investigate a new class of graph maps, called backward edge-preserving maps. These are the maps between the vertex sets of graphs such that the pre-image of every edge in the target graph is an edge in the source graph. We give a complete structural characterization of such maps for both general and connected graphs. We also explore the relationship between backward edge-preserving maps, metric maps, and graph homomorphisms, and establish criteria for the intersection of these classes. Furthermore, we study a related class of graph cohomomorphisms and establish conditions under which a map can simultaneously be a homomorphism and a cohomomorphism.

A directed star is a star digraph in which the centre is either a sink or a source. With every directed star, we associate a weight \(w\left(\alpha\right)\). Let \(D\) be a digraph; and \(C\), a spanning subgraph of \(D\); in which every component is a directed star. Then \(C\) is called a directed star cover of \(D\), and the weight of \(C\) is \(w(C)=\prod_{\alpha}w\left(\alpha\right)\), where the product is taken over all the components \(\alpha\) of \(C\). The directed star polynomial of \(D\) is \[E\left(D;\mathbf{w}\right)=\sum w(C),\] where the sum is taken over all the directed star covers of \(D\). The paper establishes properties of star polynomials and establishes relationships between star polynomials, source polynomials (where all components are source stars), and sink polynomials (where all components are sink stars). Furthermore, it presents methods to compute these polynomials for general digraphs. We derive formulae for the star polynomials of rooted products of digraphs. Moreover, we establish applications of these polynomials to several domination parameters and obtain results regarding these polynomials and independent sets in undirected graphs.

Let \(G\) be an undirected graph. The \(k\)-strong labeling (coloring) number of \(G\), \(\chi_k(G)\), is the minimum number of labels (colors) necessary to label all the vertices of \(G\) so that no two vertices that are exactly of distance \(k\) apart have the same label. \(\chi_1\) is the usual chromatic number. In this article it is shown that any linear operator on the set of graphs on \(n\) vertices thar preserves \(\chi_k\) is a vertex permutation.