Search

In 2012, Ponraj et al. defined k-product cordial labeling as follows: Let f be a map from V (G) to { 0 , 1 , ... , k − 1 } where k is an integer, 1 ≤ k ≤ | V (G) |. For each edge u v assign the label f (u) f (v) (mod  k). f is called a k-product cordial labeling if | v f (i) − v f (j) | ≤ 1 , and | e f (i) − e f (j) | ≤ 1 , i , j ∈ { 0 , 1 , ... , k − 1 } , where v f (x) and e f (x) denote the number of vertices and edges, respectively, labeled with x (x = 0 , 1 , ... , k − 1). A graph that admits k-product cordial labeling is called k-product cordial graph. Later, we proved that several families of graphs are k-product cordial graphs. In this paper, we show that the product of graphs admit k-product cordial labeling. [ABSTRACT FROM AUTHOR]

In a graph G : = (V (G) , E (G)) , a subset M of the vertex set V (G) is a module (or interval, clan) of G if every vertex outside M is adjacent to all or none of M. The empty set, the singleton sets, and the full set of vertices are trivial modules. The graph G is indecomposable (or prime) if all its modules are trivial. If G is indecomposable, we say that an edge e of G is a removable edge if G − e is indecomposable (here G − e : = (V (G) , E (G) − { e })). The graph G is said to be unstable if it has no removable edges. For a positive integer k , the k th power G k of a graph G is the graph obtained from G by adding an edge between all pairs of vertices of G with distance at most k. A graph G of order n (i.e., | V (G) | = n) is said to be p -placeable into G k , if G k contains p edge-disjoint copies of G. In this paper, we answer a question, suggested by Boudabbous in a personal communication, concerning unstable graphs and packing into their fifth power as follows: First, we give a characterization of the unstable graphs which is deduced from the results given by Ehrenfeucht, Harju and Rozenberg (the theory of 2 -structures: a framework for decomposition and transformation of graphs). Second, we prove that every unstable graph G is 2 -placeable into G 5 . [ABSTRACT FROM AUTHOR]

Let R be a commutative ring and Z (R) be its zero-divisors set. The zero-divisor graph of R , denoted by Γ (R) , is an undirected graph with vertex set Z (R) ∗ = Z (R) ∖ { 0 } and two distinct vertices a and b are adjacent if and only if a b = 0. In this paper, for n = p R q S where p and q are primes (p < q) and R and S are positive integers, we calculate the A α spectrum of the graphs Γ (ℤ n). [ABSTRACT FROM AUTHOR]

Let d (x , y) denote the length of a shortest path between vertices x and y in a graph G with vertex set V. For a positive integer k , let d k (x , y) = min { d (x , y) , k + 1 } and R k { x , y } = { z ∈ V : d k (x , z) ≠ d k (y , z) }. A set S ⊆ V is a distance-k resolving set of G if S ∩ R k { x , y } ≠ ∅ for distinct x , y ∈ V. In this paper, we study the maker-breaker distance- k resolving game (MB k RG) played on a graph G by two players, Maker and Breaker, who alternately select a vertex of G not yet chosen. Maker wins by selecting vertices which form a distance- k resolving set of G , whereas Breaker wins by preventing Maker from winning. We denote by O R , k (G) the outcome of MB k RG. Let ℳ , ℬ and , respectively, denote the outcome for which Maker, Breaker, and the first player has a winning strategy in MB k RG. Given a graph G , the parameter O R , k (G) is a non-decreasing function of k with codomain { − 1 = ℬ , 0 = , 1 = ℳ }. We exhibit pairs G and k such that the ordered pair (O R , k (G) , O R , k + 1 (G)) realizes each member of the set { (ℬ ,) , (ℬ , ℳ) , (, ℳ) } ; we provide graphs G such that O R , 1 (G) = ℬ , O R , 2 (G) = and O R , k (G) = ℳ for k ≥ 3. Moreover, we obtain some general results on MB k RG and study the MB k RG played on some graph classes. [ABSTRACT FROM AUTHOR]

Assume that K j × n is a complete, and multipartite graph consisting of j partite sets and n vertices in each partite set. For given graphs G 1 , G 2 , ... , G n , the multipartite Ramsey number (M-R-number) m j (G 1 , G 2 , ... , G n) , is the smallest integer t , such that for any n -edge-coloring (G 1 , G 2 , ... , G n) of the edges of K j × t , G i contains a monochromatic copy of G i for at least one i. The size of M-R-number m j (C 3 , n K 2 ,) for j , n ≥ 2 , the size of M-R-number m j (n K 2 , m K 2) for j ≥ 2 and n , m ≥ 1 , and the size of M-R-number m j (C 3 , C 3 , n K 2) for j ≥ 2 and n ≥ 1 have been computed in several papers up to now. In this paper, we determine some lower bounds for the M-R-number m j (C 3 , C 3 , n K 2 , m K 2) for each j , n , m ≥ 2 , and some values of M-R-number m j (C 3 , C 3 , n K 2 , m K 2) for some j ≥ 2 , and each n , m ≥ 1. [ABSTRACT FROM AUTHOR]

In this paper, we obtain explicitly the r -dynamic chromatic number of the direct product of a path P m with a k -subdivision S n 1 k of a star graph, for every positive integers r , m , k and n. Particularly, it is obtained that 2 ≤ χ r (P m × S n 1 k ) ≤ 2 n + 1. [ABSTRACT FROM AUTHOR]

In a graph G = (V , E) , a module is a vertex subset M of V such that every vertex outside M is adjacent to all or none of M. For example, ∅ , { x } (x ∈ V) and V are modules of G , called trivial modules. A graph, all the modules of which are trivial, is prime; otherwise, it is decomposable. A vertex x of a prime graph G is critical if G − x is decomposable. Moreover, a prime graph with k noncritical vertices is called (− k) -critical graph. A prime graph G is k -minimal if there is some k -vertex set X of vertices such that there is no proper induced subgraph of G containing X is prime. From this perspective, Boudabbous proposes to find the (− k) -critical graphs and k -minimal graphs for some integer k even in a particular case of graphs. This research paper attempts to answer Boudabbous's question. First, we describe the (− k) -critical tree. As a corollary, we determine the number of nonisomorphic (− k) -critical tree with n vertices where k ∈ { 1 , 2 , ⌊ n 2 ⌋ }. Second, we provide a complete characterization of the k -minimal tree. As a corollary, we determine the number of nonisomorphic k -minimal tree with n vertices where k ≤ 3. [ABSTRACT FROM AUTHOR]

Let k ≥ 1 be an integer and G be a simple graph with vertex set V (G). Let f be a function that assigns label from the set { 0 , 1 , 2 , ... , k + 1 } to the vertices of a graph G. For a vertex v ∈ V (G) , the active neighborhood of v , denoted by AN (v) , is the set of vertices w ∈ N G (v) such that f (w) ≥ 1. A [ k ] -RDF is a function f : V (G) → { 0 , 1 , 2 , ... , k + 1 } satisfying the condition that for any vertex v ∈ V (G) with f (v) < k , f (N G [ v ]) ≥ | AN (v) | + k. The weight of a [ k ] -RDF is ω (f) = Σ v ∈ V (G) f (v). The [ k ] -Roman domination number γ [ k R ] (G) of G is the minimum weight of an [ k ] -RDF on G. The case k = 4 is called quadruple Roman domination number. In this paper, we first establish an upper bound for quadruple Roman domination number of graphs with minimum degree two, and then we derive a Nordhaus–Gaddum bound on the quadruple Roman domination number of graphs. [ABSTRACT FROM AUTHOR]

Polyadic constacyclic codes over finite fields have been of interest due to their nice algebraic structures, good parameters, and wide applications. Recently, the study of Type-I m-adic constacyclic codes over finite fields has been established. In this paper, a family of Type-II m-adic constacyclic codes is investigated. The existence of such codes is determined using the length of orbits in a suitable group action. A necessary condition and a sufficient condition for a positive integer s to be a multiplier of a Type-II m-adic constacyclic code are determined. Subsequently, for a given positive integer m, a necessary condition and a sufficient condition for the existence of Type-II m-adic constacyclic codes are derived. In many cases, these conditions become both necessary and sufficient. For the other cases, determining necessary and sufficient conditions is equivalent to the discrete logarithm problem which is considered to be computationally intractable. Some special cases are investigated together with examples of Type-II polyadic constacyclic codes with good parameters. [ABSTRACT FROM AUTHOR]

Let n = p 1 α 1 p 2 α 2 ... p r α r p r + 1 α r + 1 ... p v α v , where p 1 , p 2 , ... , p v are distinct odd primes, be an integer and F q be a finite field of order q with gcd (q , n) = 1. We determine the weight enumerators of all irreducible cyclic codes of length n over F q when multiplicative order of q modulo p i α i is p i β i ; 1 ≤ i ≤ r and 2 p i β i ; r + 1 ≤ i ≤ v , where 0 ≤ β i ≤ α i − 1. [ABSTRACT FROM AUTHOR]

Let R be the ring F q [ u , v , w ] / 〈 u 2 − 1 , v 2 − 1 , w 3 − w , u v − v u , v w − w v , w u − u w 〉 , where q = p m for any odd prime p and positive integer m. In this paper, we study constacyclic codes over the ring R. We define a Gray map by a matrix and decompose a constacyclic code over the ring R as the direct sum of constacyclic codes over F q , we also characterize self-dual constacyclic codes over the ring R and give necessary and sufficient conditions for constacyclic codes to be dual-containing. As an application, we give a method to construct quantum codes from dual-containing constacyclic codes over the ring R. [ABSTRACT FROM AUTHOR]

A signed graph is a pair (G , σ) , where G is a graph and σ : E (G) → { 1 , − 1 } is a signature of G. A set S of integers is symmetric if i ∈ S implies that − i ∈ S. Given a list assignment L of G , an L -coloring of a signed graph (G , σ) is a coloring f of (G , σ) such that f (v) ∈ L (v) for each v ∈ V (G) and f (u) ≠ σ (u v) f (v) for every edge u v ∈ E (G). The signed choice number ch ± (G) of a graph G is defined to be the minimum integer k such that for any k -list assignment L of G and for any signature σ on G , there is a proper L -coloring of (G , σ). List signed coloring is a generalization of list coloring. However, the difference between signed choice number and choice number can be arbitrarily large. Hu and Wu [Planar graphs without intersecting 5 -cycles are 4 -choosable, Discrete Math. 340 (2017) 1788–1792] showed that every planar graph without intersecting 5-cycles is 4-choosable. In this paper, we prove that ch ± (G) ≤ 4 if G is a planar graph without intersecting 5-cycles, which extends the main result of [D. Hu and J. Wu, Planar graphs without intersecting 5 -cycles are 4 -choosable, Discrete Math. 340 (2017) 1788–1792]. [ABSTRACT FROM AUTHOR]

For any integer k ≥ 1 , a minus total k -dominating function is a function f : V (G) → { − 1 , 0 , 1 } satisfying ∑ w ∈ N (v) f (w) ≥ k for every v ∈ V (G) , where N (v) = { u ∈ V (G) | u v ∈ E (G) }. The minimum of the values of ∑ v ∈ V (G) f (v) , taken over all minus total k -dominating functions f , is called the minus total k -domination number and is denoted by γ t k − (G). In this paper, we initiate the study of minus total k -domination in graphs, and we present different sharp bounds on γ t k − (G). In addition, we determine the minus total k -domination number of some classes of graphs. Some of our results are extensions of known properties of the minus total domination number γ t − (G) = γ t 1 − (G). [ABSTRACT FROM AUTHOR]

For a proper k -edge coloring ϕ : E (G) → { 1 , 2 , ... , k } of a graph G , let w (v) denote the sum of the colors taken on the edges incident to the vertex v. Given a positive integer p , the Σ p -neighbor sum distinguishing k -edge coloring of G is ϕ such that for each edge u v ∈ E (G) , | w (v) − w (u) | ≥ p. We denote the smallest integer k in such coloring of G by χ Σ p ′ (G). For p = 1 , Wang et al. proved that χ Σ 1 ′ (G) ≤ max { Δ (G) + 1 0 , 2 5 }. In this paper, we show that if G is a planar graph without isolated edges, then χ Σ p ′ (G) ≤ max { Δ (G) + (1 6 p − 6) , f (p) } , where f (p) = max { 2 2 p + 3 , 8 p 2 + 2 6 p + 1 + (2 p + 1) 1 6 p 2 + 9 6 p − 1 5 4 }. [ABSTRACT FROM AUTHOR]

This paper proves that for any integer k ≥ 1 , every planar graph G of girth at least 8 k − 3 has fractional DP-chromatic number at most 2 + 1 k . [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) and a finite set T of positive integers containing 0 , a T -coloring of G is a function f : V (G) → Z + ∪ { 0 } for all u ≠ w in V (G) such that if u w ∈ E (G) then | f (u) − f (w) | ∉ T. For a T -coloring f of G , the f -span sp T f (G) is the maximum value of | f (u) − f (w) | over all pairs u , w of vertices of G. The T -span sp T (G) is the minimum f -span overall T -colorings of G. The f -edge span of a T -coloring esp T f (G) is the maximum value of | f (u) − f (w) | over all edges u w of G. The T -edge span esp T (G) is the minimum f -edge span overall T -colorings of G. This paper discusses the T -span and T -edge span of Cartesian, Join, Union and Tensor products of graphs. Also, we discuss the relation between Restricted span and Restricted edge span of graphs. [ABSTRACT FROM AUTHOR]

An L (3 , 1) -labeling of a graph Γ is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least 3 , and when u and v are not adjacent but there is a two-hop path between them, then they receive labels that differ by at least one. The span λ of such a labeling is the difference between the largest and the smallest vertex labels assigned. Let λ 3 1 (Γ) denote the least λ such that Γ admits an L (3 , 1) -labeling using labels from { 0 , 1 , ... , λ }. A Cayley graph of group G is called circulant graph of order n , if G = ℤ n . In this paper initially we investigate the L (3 , 1) -labeling for circulant graphs with "large" connection sets, and then we extend our observation and find the span of L (3 , 1) -labeling for any circulants of order n. [ABSTRACT FROM AUTHOR]

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 Δ , then la 2 (G) ≤ ⌈ Δ + 1 2 ⌉ + 6. [ABSTRACT FROM AUTHOR]

Graph labeling deals with assigning labels to one or more elements of a graph. It has a wide variety of applications including: coding theory, communication network addressing, data base management system and secret sharing schemes to mention a view. A mapping λ is called a sum labeling of a graph H (V (H) , E (H)) if it is an injection from V (H) to a set of positive integers, such that { x , y } ∈ E (H) if and only if there exists a vertex w ∈ V (H) such that λ (w) = λ (x) + λ (y). In this case, w is called a working vertex. In general, a graph G will require some isolated vertices to be labeled in this way. The least possible number of such isolated vertices is called the sum number of G ; denoted by σ (G). A sum labeling of a graph G is said to be optimum if it labels G by using σ (G) isolated vertices. In this paper, we investigate the lower bounds for the number of isolates required by an even fan and an odd fan, and then we construct optimum sum labelling for the graphs to prove: σ (F n) = 3 for even  n , n ≥ 4 , and for  n = 3 4 for odd  n , n ≥ 5. [ABSTRACT FROM AUTHOR]

In this study, unlike other power sequences, we define new ones in the integer and integer-valued polynomial module. We call these sequences the power-generalized k -Horadam sequence in the integer module and the power-generalized k -Horadam sequence in the integer-valued polynomial module. Using these sequences, we rebuild the ElGamal cryptosystem and then obtain a new cryptographic method by combining this and symmetric systems. We provide an encryption example where our method is applied. Finally, we see the advantages of the new cryptographic method when we compare the obtained new cryptographic method with some of the asymmetric cryptographic systems such as RSA and ElGamal. And we achieve that new cryptographic method that has more advantageous. [ABSTRACT FROM AUTHOR]

For a connected graph G of order p and a set S ⊆ V (G) , the Steiner distance of S is the minimum number of edges in a connected subgraph of G containing S. If n is an integer, 2 ≤ n ≤ p and a vertex v ∈ V (G) , the Steiner n -eccentricity of a vertex v of G , ex n (v) , is the maximum Steiner distance of all n -subsets of V (G) containing v. The Steiner n -radius of G , rad n (G) , is the minimum Steiner n -eccentricities of all vertices in G. We give bounds on rad n (G) in terms of the order of G and the minimum degree of G for all graphs and for graphs that contain no triangles. We shall also investigate the relation between the n -radius of a graph G and its complement Ḡ. [ABSTRACT FROM AUTHOR]

For a connected graph G = (V , E) of order at least two, a total outer connected geodetic set  S of a graph G is an outer connected geodetic set such that the subgraph induced by S has no isolated vertices. The minimum cardinality of a total outer connected geodetic set of G is the total outer connected geodetic number of G and is denoted by cg to (G). We determine bounds for it and also find the total outer connected geodetic number for some special classes of graphs. It is shown that for positive integers r , d and k ≥ 4 with r < d ≤ 2 r , there exists a connected graph G with rad (G) = r , diam (G) = d and cg to (G) = k. It is proved that for each triple p , d and k of positive integers with k ≥ 4 , d ≥ 2 and p − d − k + 2 ≥ 0 , there exists a connected graph G of order p such that diam (G) = d and cg to (G) = k. It is also shown that for positive integers a , b such that 3 ≤ a ≤ b with b ≤ 2 a , there exists a connected graph G such that g oc (G) = a and cg to (G) = b , where g oc (G) is the outer connected geodetic number of a graph G. [ABSTRACT FROM AUTHOR]

For a connected graph G of order at least two, a double geodetic set S of a graph G is a restrained double geodetic set if either S = V or the subgraph induced by V − S has no isolated vertices. The minimum cardinality of a restrained double geodetic set of G is the restrained double geodetic number of G and is denoted by dg r (G). The restrained double geodetic number of some standard graphs is determined. It is proved that for a nontrivial connected graph G , g r (G) = 2 if and only if dg r (G) = 2. It is shown that for any three positive integers a , b , c with 4 ≤ a ≤ b ≤ c , there is a connected graph G with g (G) = a , g r (G) = b and dg r (G) = c , where g (G) is the geodetic number and g r (G) is the restrained geodetic number of a graph G. It is also shown that for every pair a, b of positive integers with 4 ≤ a ≤ b , there is a connected graph G with dg (G) = a and dg r (G) = b , where dg (G) is the double geodetic number of a graph G. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a partition π = (V 1 , V 2 , ... , V k) of the vertex set V is a transitive partition if V i dominates V j whenever i < j. The transitivity  Tr (G) of a graph G is the maximum order of a transitive partition of V. For any positive integer k , we characterize the smallest tree with transitivity k and obtain an algorithm to determine the transitivity of any tree of finite order. [ABSTRACT FROM AUTHOR]