Discrete Mathematics, Algorithms and Applications

For a finite commutative ring R and a positive integer k, let G(R, k) denote the digraph whose set of vertices is R and for which there is a directed edge from a to a^k. The digraph G(R, k) is called symmetric of order M if its set of connected components can be partitioned into subsets of size M with each subset containing M isomorphic components. We primarily aim to factor G(R, k) into the product of its subdigraphs. If the characteristic of R is a prime p, we obtain several sufficient conditions for G(R, k) to be symmetric of order M.

Let ℕ₀ be the set of all non-negative integers. An integer additive set-indexer (IASI) of a graph G is an injective function f : V(G) → 2^ℕ₀ such that the induced function g_f : E(G) → 2^ℕ₀ defined by f⁺(uv) = f(u) + f(v) is also injective. An IASI is said to be k-uniform if |f⁺(e)| = k for all e ∈ E(G). In this paper, we introduce the notions of strong IASIs and initiate a study of the graphs which admit strong IASIs.

Partition of G into edge-disjoint H-factors is called an H-factorization of G. Shehzad Afzal and Clemens Brand have factorized graphs into factors which are isomorphic to triangulated Cartesian product of two subgraphs. Also they have discussed properties of triangulated Cartesian product of more than two graphs. In this paper, we show that the necessary conditions mn ≡ 0 (mod 3), m, n are odd and 3(mn + m + n - 3) ≡ 0 (mod 8) are sufficient for the existence of a P₃-factorization of K_m ⧅ K_n, where ⧅ denotes triangulated Cartesian product of graphs, if one of the following holds:

(i) m ≡ 9 (mod 12), n = 5, 13 and 17,

(ii) m ≡ 9 (mod 12), n^s, s > 1, n = 5, 13 and 17,

(iii) m ≡ 9 (mod 12), n = p^sq^t for all s, t ≥ 1, where p = 5, 13 and q = 13, 17, p ≠ q,

(iv) m ≡ 9 (mod 12), n ≡ 9 (mod 12).

Let R be a commutative ring. The intersection graph of gamma sets in the zero-divisor graph Γ(R) of R is the graph I_Γ(R) with vertex set as the collection of all gamma sets of the zero-divisor graph Γ(R) of R and two distinct vertices A and B are adjacent if and only if A ∩ B ≠ ∅. In this paper, we study about various properties of I_Γ(R) and investigate the interplay between the graph theoretic properties of I_Γ(R) and the ring theoretic properties of R.

Let R be a ring with the identity element 1, α be an endomorphism of R and δ be a left α-derivation. In this paper, we introduce a generalization of a commuting graph, which is denoted by Γ_R(α, δ), as a directed graph with vertex set R and, for two distinct vertices x and y, there is an arc from x to y if and only if xy = α(y)x + δ(y). We study some basic properties of Γ_R(α, δ). Also, we investigate the planarity and genus of the graph Γ_R(α, 0).

A vertex-deleted subgraph of a graph G is called a card of G. A card of G with which the degree of the deleted vertex is also given is called a degree associated card or dacard of G. The adversary degree associated reconstruction number of a graph G, adrn(G), is the minimum number k such that every collection of k dacards of G uniquely determines G. We prove that adrn(G) = 1 + min{t+1, m-t} or 1 + min{t, m - t + 2} for a graph G obtained by subdividing t edges of K_{1, m}. We also prove that if G is a nonempty disconnected graph whose components are cycles or complete graphs, then adrn(G) is 3 or 4, while, if G is a double star whose central vertices have degrees m + 1 and n + 1(m > n ≥ 2), then adrn(G) can be as large as n + 3.

This paper is concerned with two arithmetical functions namely remainder sum function and quotient sum function which are respectively the sequences A004125 and A006218 in Online Encyclopedia of Integer Sequences. The remainder sum function is defined by for every positive integer n, and quotient sum function is defined by where q(n, i) is the quotient obtained when n is divided by i. We establish few divisibility properties these functions enjoy and we found their bounds. Furthermore, we define restricted remainder sum function by R_A(n) = ∑_k∈A n mod k where A is a set of positive integers and we define restricted quotient sum function by Q_A(n) = ∑_k∈A q(n, k). The function Q_A(n) is found to be a quasi-polynomial of degree one when A is a finite set of positive integers and R_A(n) is found to be a periodic function with period ∏_a∈A a. Finally, the above defined four functions found to have recurrence relation whose derivation requires few results from integer partition theory.

The zero forcing number, Z(G), of a graph G is the minimum cardinality of a set S of black vertices (whereas vertices in V(G)\S are colored white) such that V(G) is turned black after finitely many applications of "the color-change rule": a white vertex is converted to a black vertex if it is the only white neighbor of a black vertex. Zero forcing number was introduced and used to bound the minimum rank of graphs by the "AIM Minimum Rank-Special Graphs Work Group". It is known that Z(G) ≥ δ(G), where δ(G) is the minimum degree of G. We show that Z(G) ≤ n - 3 if a connected graph G of order n has a connected complement graph . Further, we characterize a tree or a unicyclic graph G which satisfies either or .

To monitor an electric power system by placing as few phase measurement units (PMUs) as possible is closely related to the famous vertex cover problem and domination problem in graph theory. A set P is a power dominating set (PDS) of a graph G = (V, E), if every vertex and every edge in the system is observed following the observation rules of power system monitoring. The minimum cardinality of a PDS of a graph G is the power domination number γ_p(G). In this paper, we determine the upper bounds of power domination number of generalized undirected de Bruijn graphs and generalized undirected Kautz graphs.

Let R be a commutative ring and Z(R) be the set of all zero-divisors of R. The total graph of R, denoted by T_Γ(R), is the (undirected) graph with vertices set R. For any two distinct elements x, y ∈ R, the vertices x and y are adjacent if and only if x + y ∈ Z(R). In this paper, we obtain certain fundamental properties of the total graph of ℤ_n × ℤ_m, where n and m are positive integers. We determine the clique number and independent number of the total graph T_Γ(ℤ_n × ℤ_m).

The concept of energy of a graph was first defined in 1978 by Gutman as the sum of the absolute values of the eigenvalues of its adjacency matrix. Let λ₁, λ₂, …, λ_n be eigenvalues of graph Γ, then the Estrada index of Γ is defined as . The aim of this paper is to estimate the energy and Estrada index of Cayley graphs Cay(G, S) where G ≅ D_2n, U_6n and S is a normal symmetric generating subset of G.