We consider a vertex-coloring problem where the amount one pays for using a color is a function of how many times the color is used. For a cost-function \(f\), we define the \(f\)-chromatic number of graph \(G\) as the minimum cost of a (proper) coloring of \(G\), and focus on the case that the marginal costs \(f(i+1)-f(i)\) are non-increasing. We provide bounds for general graphs, for specific classes of graphs, and for some operations on graphs. We also consider the number of colors used in an optimal coloring, and for example, characterize the trees where the bipartite coloring is not always optimal.

Let \(q\) be a positive integral power of some prime \(p\) and \(\mathbb{F}_{q^m}\) be a finite field with \(q^m\) elements for some \(m \in \mathbb{N}\). Here we establish a sufficient condition for the existence of primitive normal pairs of the type \((\epsilon, f(\epsilon))\) in \(\mathbb{F}_{q^m}\) over \(\mathbb{F}_{q}\) with two prescribed traces, \(\text{Tr}_{{\mathbb{F}_{q^m}}/{\mathbb{F}_q}}(\epsilon)=a\) and \(\text{Tr}_{{\mathbb{F}_{q^m}}/{\mathbb{F}_q}}(f(\epsilon))=b\), where \(f(x) \in \mathbb{F}_{q^m}(x)\) is a rational function with some restrictions and \(a, b \in \mathbb{F}^*_q\). Furthermore, for \(q=5^k\), \(m \geq 9\) and rational functions with degree sum 4, we explicitly find at most 13 fields in which the desired pair may not exist.

Let \(G = (V(G), E(G))\) be a simple connected graph. The inverse sum indeg index of \(G\), denoted by \(\text{ISI}(G)\), is defined as the sum of the weights \(\frac{d(u)d(v)}{d(u) + d(v)}\) of all edges \(uv\) of \(G\), where \(d(u)\) denotes the degree of a vertex in \(G\). In this paper, we first present some lower and upper bound for \(ISI\) index in terms of graph parameters such as maximum degree, minimum degree and clique number. Moreover, we compute \(ISI\) index of several graph operations like join, cartesian product, composition, corona and strong product of graphs.

We consider the eternal distance-2 domination problem, recently proposed by Cox, Meger, and Messinger, on trees. We show that finding a minimum eternal distance-2 dominating set of a tree is linear time in the order of the graph by providing a fast algorithm. Additionally, we characterize trees that have eternal distance-2 domination number equal to their domination number or their distance-2 domination number, {along with trees that are} eternal distance-2 domination critical. We conclude by providing general upper and lower bounds for the eternal distance-k domination number of a graph. We construct an infinite family of trees which meet said upper bound and another infinite family of trees whose eternal distance-k domination number is within a factor of 2 of the given lower bound.

We apply the splitting operation defined on binary matroids (Raghunathan et al., 1998) to \(p\)– matroids, where \(p\)-matroids refer to matroids representable over \(GF(p).\) We also characterize circuits, bases, and independent sets of the resulting matroid. Sufficient conditions to yield Eulerian \(p\)-matroids from Eulerian and non-Eulerian \(p\)-matroids by applying the splitting operation are obtained. A class of connected \(p\)-matroids that gives connected \(p\)-matroids under the splitting operation is characterized. In Application, we characterize a class of paving \(p\)-matroids, which produces paving matroids after the splitting operation.

For a connected graph \(G=(V,E)\) of order at least two, a \(u-v\) chordless path in \(G\) is a \(monophonic\) \(path\). The edge monophonic closed interval \(I_{em}[u,v]\) consists of all the edges lying on some \(u-v\) monophonic path. For \(S'\subseteq V(G),\) the set \(I_{em}[S']\) is the union of all sets \(I_{em}[u,v]\) for \(u,v\in S'.\) A set \(S'\) of vertices in \(G\) is called an \(edge\) \(monophonic\) \(set\) of \(G\) if \(I_{em}[S']=E(G).\) The edge monophonic number \({m_1}(G)\) of G is the minimum cardinality of its edge monophonic sets of \(G\). In this paper the monophonic number and the edge monophonic number of corona product graphs are obtained. Exact values are determined for several classes of corona product graphs.

The stretched Littlewood-Richardson coefficient \(c^{t\nu}_{t\lambda,t\mu}\) was conjectured by King, Tollu, and Toumazet to be a polynomial function in \(t\). It was shown to be true by Derksen and Weyman using semi-invariants of quivers. Later, Rassart used Steinberg’s formula, the hive conditions, and the Kostant partition function to show a stronger result that \(c^{\nu}_{\lambda,\mu}\) is indeed a polynomial in variables \(\nu, \lambda, \mu\) provided they lie in certain polyhedral cones. Motivated by Rassart’s approach, we give a short alternative proof of the polynomiality of \(c^{t\nu}_{t\lambda,t\mu}\) using Steinberg’s formula and a simple argument about the chamber complex of the Kostant partition function.

In this work, we study type B set partitions for a given specific positive integer \(k\) defined over \(\langle n \rangle = \{-n, -(n-1), \cdots, -1, 0, 1, \cdots, n-1, n\}\). We found a few generating functions of type B analogues for some of the set partition statistics defined by Wachs, White and Steingrímsson for partitions over positive integers \([n] = \{1, 2, \cdots, n\}\), both for standard and ordered set partitions respectively. We extended the idea of restricted growth functions utilized by Wachs and White for set partitions over \([n]\), in the scenario of \(\langle n \rangle\) and called the analogue as Signed Restricted Growth Function (SRGF). We discussed analogues of major index for type B partitions in terms of SRGF. We found an analogue of Foata bijection and reduced matrix for type B set partitions as done by Sagan for set partitions of \([n]\) with specific number of blocks \(k\). We conclude with some open questions regarding the type B analogue of some well known results already done in case of set partitions of \([n]\).

Suppose that \(\phi\) is a proper edge-\(k\)-coloring of the graph \(G\). For a vertex \(v \in V(G)\), let \(C_\phi(v)\) denote the set of colors assigned to the edges incident with \(v\). The proper edge-\(k\)-coloring \(\phi\) of \(G\) is strict neighbor-distinguishing if for any adjacent vertices \(u\) and \(v\), \(C_\phi(u) \varsubsetneq C_\phi(v)\) and \(C_\phi(v) \varsubsetneq C_\phi(u)\). The strict neighbor-distinguishing index, denoted \(\chi’_{snd}(G)\), is the minimum integer \(k\) such that \(G\) has a strict neighbor-distinguishing edge-\(k\)-coloring. In this paper we prove that if \(G\) is a simple graph with maximum degree five, then \(\chi’_{snd}(G) \leq 12\).

Let \(2 \le k \in \mathbb{Z}\). A total coloring of a \(k\)-regular simple graph via \(k+1\) colors is an efficient total coloring if each color yields an efficient dominating set, where the efficient domination condition applies to the restriction of each color class to the vertex set. In this work, focus is set upon graphs of girth \(k+1\). Efficient total colorings of finite connected simple cubic graphs of girth 4 are constructed starting at the 3-cube. It is conjectured that all of them are obtained by means of four basic operations. In contrast, the Robertson 19-vertex \((4,5)\)-cage, the alternate union \(Pet^k\) of a (Hamilton) \(10k\)-cycle with \(k\) pentagon and \(k\)-pentagram 5-cycles, for \(k > 1\) not divisible by 5, and its double cover \(Dod^k\), contain TCs that are nonefficient. Applications to partitions into 3-paths and 3-stars are given.