Discrete Mathematics, Algorithms and Applications

A proper vertex coloring of a graph $G$ is called a star coloring if every path on four vertices in $G$ is not 2-colored. The star chromatic number is the minimum number of colors required to star color $G$ and it is denoted by ${\chi }_s(G)$. In this paper, the star coloring of Harary graphs $H_{k,m}$, where $k$ is even and $m$ is odd, is discussed.

Let ${𝔽}_q$ be a finite field with $q$ elements. Let $n$ be a positive integer with radical $\mathrm{\text{rad}}(n)$, namely, the product of distinct prime divisors of $n$. If the order of $q$ modulo $\mathrm{\text{rad}}(n)$ is either 1 or a prime, then the irreducible factorization and a counting formula of irreducible factors of $x^n-1$ over ${𝔽}_q$ were obtained by Martínez, Vergara and Oliveira, Explicit factorization of $x^n-1\in {𝔽}_q[x]$, Des. Codes Cryptogr. 77(1) (2015) 277–286 and Wu, Yue and Fan, Further factorization of $x^n-1$ over a finite field, Finite Fields Appl. 54 (2018) 197–215. In this paper, we explicitly factorize $x^n-1$ into irreducible factors in ${𝔽}_q[x]$ and calculate the number of the irreducible factors when the order of $q$ modulo $\mathrm{\text{rad}}(n)$ is a product of two primes.

Sampathkumar [F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969)] defined the coloring of a digraph $D=(V,A)$ as a coloring of its vertices by the following rule: Let $uv$ be an arc in $D$. If the tail $u$ is colored first, then the head $v$ should receive a color different from that of $u$. But, if $v$ is colored first, then $u$ may or may not receive the color of $v$. The dichromatic number ${\chi }_d(D)$ of a digraph $D$ is the minimum number of colors needed for coloring of a digraph $D$. In this paper, we obtain some results on uniquely colorable digraphs and Nordhaus–Gaddum type results for digraphs.

Let $G=(V,E)$ be a simple finite and connected graph. A dominating set $D\subseteq V(G)$ is a strong nonsplit dominating set if the induced subgraph $〈V-D〉$ is complete. $D^{-1}\subseteq V-D$ is an inverse strong nonsplit dominating set if $D^{-1}$ is a strong nonsplit dominating set of $G$. The cardinality of minimum inverse strong nonsplit dominating set is the inverse strong nonsplit domination number ${\gamma }_{\mathrm{\text{sns}}}^{-1}(G)$. In this paper, we initiated and introduced a new variant of strong nonsplit dominating set called inverse strong nonsplit dominating set. Also, we obtain the inverse strong nonsplit domination number and bounds of some standard graphs and its complement.

We confirm the following conjecture which has been proposed by Stanić in [I. Jovanović and Z. Stanić, Spectral distances of graphs, Linear Algebra Appl. 436(5) (2012) 1425–1435]:

Let $G=(V,E)$ be a graph. A subset $S$ of $V$ is called a dominating set of $G$ if every vertex not in $S$ is adjacent to some vertex in $S$. The domination number $\gamma (G)$ of $G$ is the minimum cardinality taken over all dominating sets of $G$. The shadow graph of $G$, denoted $D_2(G)$ is the graph constructed from $G$ by taking two copies of $G$ namely $G$ itself and $G^{\prime }$ and by joining each vertex $u$ in $G$ to the neighbors of the corresponding vertex $u^{\prime }$ in $G^{\prime }$. In this paper, we obtain the upper and lower bounds for the sum of domination number of a graph and its shadow graph and characterize such extremal graphs.

For a connected graph $G$, the Mostar index is defined as $\mathrm{\text{Mo}}(G)={\sum }_{xy\in E(G)}|n_x-n_y|$, where $n_x$ (respectively, $n_y$) is the number of vertices of $G$ closer to $x$ (respectively, $y$) than $y$ (respectively, $x$). In this paper, we determine the first five maximal (respectively, the first five minimal) values of the Mostar index among all phenylene chains with $h$ hexagons, the corresponding extremal chains are completely characterized, respectively.

The end-to-end learning approaches possess the advantages of high efficiency, rapidity and superior solving precision for combinatorial optimization problems, while exploring generalization to instances different from training scale is an open question. In this paper, we focus on the knapsack problem (KP) and employ an end-to-end data-driven approach based on attention model incorporated with different forms of baseline of policy gradient algorithm to solve KP. We first investigate the generalization performance of the proposed approach for KP on various problem scales with different capacities. The experimental results show that the end-to-end model possesses certain learning and generalization abilities to discover the intrinsic characteristics between instances, then guides to solve other instances of different scales.

Let $G$ be a graph and $\overline{G}$ be the complement of $G$. The complementary prism $G\overline{G}$ of $G$ is the graph formed from the disjoint union of $G$ and $\overline{G}$ by adding the edges of a perfect matching between the corresponding vertices of $G$ and $\overline{G}$. A subset $S$ of vertices in a connected graph $G$ is called a geodetic hop dominating set of $G$ if $S$ is both a geodetic set and a hop dominating set of $G$. The minimum cardinality of a geodetic hop dominating set of $G$ is its geodetic hop domination number and is denoted by ${\gamma }_{hg}(G)$. In this paper, we study the geodetic hop domination number of complementary prisms.

The linear 2-arboricity la${}_2(G)$ of a graph $G$ is the least integer $k$ such that $G$ can be partitioned into $k$ edge-disjoint forests, whose component trees are paths of length at most 2. In this paper, we prove that if $G$ is a 1-planar graph without 3-cycles and with maximum degree $\mathrm{\Delta }$, then la${}_2(G)\le \lceil \frac{\mathrm{\Delta }+1}{2}\rceil +6$.

Let $G$ be a finite simple graph. The middle graph $M(G)$ of a graph $G$ is the graph obtained by subdividing each edge of $G$ exactly once and joining all these newly introduced vertices of adjacent edges of $G$. The middle domination number ${\gamma }^{\star }(G)$ of $G$ is defined by the domination number $\gamma (M(G))$ of the middle graph $M(G)$. A subset $S$ of $V(G)$ is a 2-independent set of $G$ if every vertex of $S$ has at most one neighbor in $S$. The maximum cardinality of a 2-independent set of $G$ is the 2-independence number ${\beta }_2(G)$. These parameters are incomparable in general. However, we show that ${\gamma }^{\star }(T)\le {\beta }_2(T)$ for any tree $T$. We also characterize all trees attaining the equality.

Let $G$ be a graph with $n$ vertices and $m$ edges. The minimum edge dominating energy is equal to the sum of the absolute values of eigenvalues of the minimum edge dominating matrix of graph $G$. In this paper, we establish some bounds for the minimum edge dominating energy of subgraphs of a graph.

For a connected graph $G(V,E)$ and a fixed integer $r>0$, a node $q\in V$ $r$-dominates another node $s\in V$ if $d(q,s)\le r$. An edge $(q,s)$ is $r$-neighborhood covered by a vertex $t$, if $d(q,t)\le r$ and $d(s,t)\le r$, i.e., both the vertices $q$ and $s$ are $r$-dominated by the vertex $t$. A set $C_r\subseteq V$ is known to be a $r$-neighborhood covering ($r$-NC) set of graph $G$ if and only if one or more vertices of $C_r$ $r$-dominate each edge in E. Among all $r$-NC sets of graph $G$, the set with fewest cardinality is the minimum r-NC set of $G$ and we indicate its cardinality as $r$-NC-number and we denote it by the symbol $\rho (G,r)$. This is an NP-complete problem on general graphs. It is also NP-complete for chordal graphs. Here, we develop an $O(n)$ time algorithm for computing a minimum $r$-NC set of permutation graphs, where $n$ indicates the order of the set $V$.

The non-commuting graph ${\mathrm{\Gamma }}_G$ of a finite group $G$ has vertex set as $G\setminus Z(G)$ and any two vertices $x,y$ are adjacent if $xy\ne yx$. In this paper, we have determined the metric dimension and resolving polynomial of ${\mathrm{\Gamma }}_{D_n}$, where $D_n$ is the dihedral group of order $2n$. The distance spectrum of ${\mathrm{\Gamma }}_{D_n}$ has also been determined for all $n>2$.

Graphs considered here are simple, finite and undirected. A graph is denoted by $G$ and it has vertex set $V(G)$ and edge set $E(G)$. Inspired by two concepts, this paper comes into existence. One is the degree equitability in graphs conceived by Prof. E. Sampathkumar and the other is fair domination (that is, vertices outside the dominating set are dominated by equal number of vertices) [Y. Caro, A. Hansberg and M. Henning, Fair domination in graphs, Discrete Math. 312 (2012) 2905–2914], Equitable fair domination is studied here.

In this paper, we construct a new framework that’s we call the weighted $3$-simplicial complex and we define its spectral gap. An upper bound for our spectral gap is given by generalizing the Cheeger constant. The lower bound for our spectral gap is obtained from the first nonzero eigenvalue of the Laplacian acting on the functions of certain weighted $2$-simplicial complexes.

In the online metric matching problem, there are servers on a given metric space and requests are given one-by-one. The task of an online algorithm is to match each request immediately and irrevocably with one of the unused servers. In this paper, we pursue competitive analysis for two variants of the online metric matching problem. The first variant is a restriction where each server is placed at one of two positions, which is denoted by OMM($2$). We show that a simple greedy algorithm achieves the competitive ratio of 3 for OMM($2$). We also show that this greedy algorithm is optimal by showing that the competitive ratio of any deterministic online algorithm for OMM($2$) is at least 3. The second variant is the online facility assignment problem on a line. In this problem, the metric space is a line, the servers have capacities, and the distances between any two consecutive servers are the same. We denote this problem by OFAL($k$), where $k$ is the number of servers. We first observe that the upper and lower bounds for OMM($2$) also hold for OFAL($2$), so the competitive ratio for OFAL($2$) is exactly 3. We then show lower bounds on the competitive ratio $1+\sqrt{6}$ $(>3.44948)$, $\frac{4+\sqrt{73}}{3}$ $(>4.18133)$ and $\frac{13}{3}$ $(>4.33333)$ for OFAL($3$), OFAL($4$) and OFAL($5$), respectively.

In this paper, we introduce the notion of a solvable triple of binary relations on a set. This notion generalizes the notion of a regular relation and all other notions that are variants of the notion of the regularity, defined previously by many people. We also give some characterizations of the solvability of a triple of relations and use this to study Green’s relations on the monoid of binary relations on a set.