Communications in Combinatorics and Optimization
Volume:8 Issue: 4, Autumn 2023

A tractable and efficient method of solving zero-sum games played in staircase-function finite spaces is presented, where the possibility of varying the time interval on which the game is defined is considered. The time interval can be narrowed by an integer number of time subintervals and still the solution is obtained by stacking solutions of smaller-sized matrix games, each defined on a subinterval where the pure strategy value is constant. The stack is always possible, even when only time is discrete and the set of pure strategy possible values is uncountably infinite. So, the solution of the initial discrete-time staircase-function zero-sum game can be obtained by stacking the solutions of the ordinary zero-sum games defined on rectangle, whichever the time interval is. Any combination of the solutions of the subinterval games is a solution of the initial zero-sum game.

Let $G=(V,E)$ be a graph of order $n$ and size $m.$ The graph $Sp(G)$ obtained from $G$ by adding a new vertex $v'$ for every vertex $vin V$ and joining $v'$ to all neighbors of $v$ in $G$ is called the splitting graph of $G.$ In this paper, we determine the domination number, the total domination number, connected domination number, paired domination number and independent domination number for the splitting graph $Sp(G).$

Suppose each edge of a simple connected undirected graph is given a unique number from the numbers $1, 2, dots, $q$, where $q$ is the number of edges of that graph. Then each vertex is labelled with sum of the labels of the edges incident to it. If no two vertices have the same label, then the graph is called an antimagic graph. We prove that the Cartesian product of wheel graph and path graph is antimagic.

An independent Italian dominating function (IID-function) on a graph $G$ is a function $f:V(G)rightarrow{0,1,2}$ satisfying the conditions that (i) $sum_{uin N(v)}f(u)geq2$ when $f(v)=0$, and (ii) the set of all vertices assigned non-zero values under $f$ is independent. The weight of an IID-function is the sum of its function values over all vertices, and the independent Italian domination number $i_{I}(G)$ of $G$ is the minimum weight of an IID-function on $G$. In this paper, we initiate the study of the independent Italian bondage number $b_{iI}(G)$ of a graph $G$ having at least one component of order at least three, defined as the smallest size of a set of edges of $G$ whose removal from $G$ increases $i_{I}(G)$. We show that the decision problem associated with the independent Italian bondage problem is NP-hard for arbitrary graphs. Moreover, various upper bounds on $b_{iI}(G)$ are established as well as exact values on it for some special graphs. In particular, for trees $T$ of order at least three, it is shown that $b_{iI}(T)leq2$.

In the paper, by virtue of Wronski's formula and Kaluza's theorem for the power series and its reciprocal, and with the aid of the logarithmic convexity of a sequence constituted by central Delannoy numbers, the authors present negativity of several Toeplitz--Hessenberg determinants whose elements contain central Delannoy numbers and combinatorial numbers.

This paper focuses on a novel approach for producing a floor plan (FP), either a rectangular (RFP) or an orthogonal (OFP) based on the concept of orthogonal drawings, which satisfies the adjacency relations given by any bi-connected plane triangulation $G$.     Previous algorithms for constructing a FP are primarily restricted to the cases given below:     begin{enumerate}[(i)]         item A bi-connected plane triangulation without separating triangles (STs) and with at most 4 corner implying paths (CIPs), known as properly triangulated planar graph (PTPG).         item A bi-connected plane triangulation with an exterior face of length 3 and no CIPs, known as maximal planar graph (MPG).     end{enumerate}     The FP obtained in the above two cases is a RFP or an OFP respectively. In this paper, we present the construction of a FP (RFP if exists, else an OFP), for a bi-connected plane triangulation $G$ in linear-time.

A local antimagic edge labeling of a graph $G=(V,E)$ is a bijection $f:Erightarrow{1,2,dots,|E|}$ such that the induced vertex labeling $f^+:Vrightarrow mathbb{Z}$ given by $f^+(u)=sum f(e),$ where the summation runs over all edges $e$ incident to $u,$ has the property that any two adjacent vertices have distinct labels. A graph $G$ is said to be locally antimagic if it admits a local antimagic edge labeling. The local antimagic chromatic number $chi_{la}(G)$ is the minimum number of distinct induced vertex labels over all local antimagic  labelings of $G.$ In this paper we obtain sufficient conditions under which $chi_{la}(Gvee H),$ where $H$ is either a cycle or the empty graph $O_n=overline{K_n},$ satisfies a sharp upper bound. Using this we determine the value of $chi_{la}(Gvee H)$ for many wheel related graphs $G.$

Let $mathcal{S}$ be a commutative ring with unity and $A(mathcal{S})$ denotes the set of annihilating-ideals of $mathcal{S}$. The essential annihilating-ideal graph of $mathcal{S}$, denoted by $mathcal{EG}(mathcal{S})$, is an undirected graph with $A^*(mathcal{S})$ as the set of vertices and   for distinct $mathcal{I}, mathcal{J} in A^*(mathcal{S})$, $mathcal{I} sim mathcal{J}$ is an edge if and only if $Ann(mathcal{IJ}) leq_e mathcal{S}$. In this paper, we classify the Artinian rings $mathcal{S}$ for which $mathcal{EG}(mathcal{S})$ is projective. We also discuss the coloring of $mathcal{EG}(mathcal{S})$. Moreover, we discuss the domination number of $mathcal{EG}(mathcal{S})$.

Transit functions are introduced to study betweenness, intervals and convexity in an axiomatic setup on graphs and other discrete structures. Prime example of a transit function on graphs is the well studied interval function of a connected graph. In this paper, we study the Cycle transit function $mathcal{C}( u,v)$ on graphs which is a transit function derived from the interval function. We study the betweenness properties and also characterize graphs in which the cycle transit function coincides with the interval function. We also characterize graphs where $|mathcal{C}( u,v)cap mathcal{C}( v,w) cap mathcal{C}( u,w)|le 1$ as an analogue of median graphs.

The main objective of this paper is to establish as many as thirty new closed-form evaluations of the generalized hypergeometric function $_{q+1}F_q(z)$ for $q= 2, 3$. This is achieved by means of separating the generalized hypergeometric function $_{q+1}F_q(z)$ for $q=1, 2, 3$ into even and odd components together with the use of several known infinite series involving reciprocal of the non-central binomial coefficients obtained earlier by L. Zhang and W. Ji.

‎In 2021, a novel degree-based topological index was introduced by Gutman, called the  Sombor index. Recently Kulli and Gutman introduced a vertex-edge variant of the Sombor index, is caled KG-Sombor index. In this paper, we establish lower bound on the KG-Sombor index and determine the extremal trees achieve this bound.

A function $f:Vrightarrow {0,1,2}$ on a signed graph $S=(G,sigma)$  where $G = (V,E)$ is a Roman dominating function(RDF) if $f(N[v]) = f(v) + sum_{u in N(v)} sigma(uv)f(u) geq 1$ for all $vin V$ and for each vertex $v$ with $f(v)=0$ there is a vertex $u$ in $N^+(v)$ such that $f(u) = 2$. The weight of an RDF $f$ is given by $omega(f) =sum_{vin V}f(v)$ and the minimum weight among all the RDFs on $S$ is called the Roman domination number $gamma_R(S)$. Any RDF on $S$ with the minimum weight is known as a $gamma_R(S)$-function. In this article we obtain certain bounds for $ gamma_{R} $ and characterise the signed graphs attaining small values for $ gamma_R. $