Browsing by Author "Kola, S.R."

Now showing 1 - 20 of 21

A lower bound for radio ?-chromatic number of an arbitrary graph
(University of Calgary woodrow@ucalgary.ca, 2015) Kola, S.R.; Panigrahi, P.
Radio ?-coloring is a variation of Hale's channel assignment problem, in which one seeks to assign positive integers to the vertices of a graph G, subject to certain constraints involving the distance be- tween the vertices. Speciffically, for any simple connected graph G with diameter d and a positive integer ?, 1 ? ? ? d, a radio ?-coloring of G is an assignment f of positive integers to the vertices of G such that jf(u)-f(v)j ? 1+?-d(u; v), where u and v are any two distinct vertices of G and d(u; v) is the distance between u and v. In this paper we give a lower bound for the radio ?-chromatic number of an arbitrary graph in terms of k, the total number of vertices n and a positive integer M such that d(u; v)+d(v;w)+d(u;w) ? M for all u; v;w 2 V (G). If M is the triameter we get a better lower bound. We also ffind the triameter M for several graphs, and show that the lower bound obtained for these graphs is sharp for the case ? = d. © 2015 University of Calgary.
A note on bounds for the broadcast domination number of graphs
(Elsevier B.V., 2024) Sen, J.; Kola, S.R.
A dominating broadcast of a graph G is a function f:V(G)→{0,1,2,…,diam(G)} such that f(v)⩽e(v) for all v∈V(G), where e(v) is the eccentricity of v, and for every u∈V(G), there exists a vertex v with f(v)⩾1 and d(u,v)⩽f(v). The cost of f is ∑v∈V(G)f(v). The minimum cost over all the dominating broadcasts of G is called the broadcast domination number γb(G) of G. In this paper, we give new upper and lower bounds for γb(G). We show that both the bounds are tight. Also, we improve the upper bound for a subclass of regular graphs. Further, we explore the broadcast domination numbers of generalized Petersen graphs and a subclass of circulant graphs. © 2024 Elsevier B.V.
Broadcast domination of lexicographic and modular products of graphs
(Taylor and Francis Ltd., 2022) Sen, J.; Kola, S.R.
A dominating broadcast labeling of a graph G is a function (Formula presented.) such that (Formula presented.) for all (Formula presented.) where e(v) is the eccentricity of v, and for every vertex (Formula presented.) there exists a vertex v with (Formula presented.) and (Formula presented.) The cost of f is (Formula presented.) The minimum of costs over all the dominating broadcast labelings of G is called the broadcast domination number (Formula presented.) of G. In this paper, we give bounds to the broadcast domination number of lexicographic product G • H of a connected graph G and a graph H, and we show that the bounds are tight by determining the exact values for lexicographic products of some classes of graphs. Also, we give an algorithm which produces a dominating broadcast labeling of G • H. We use the algorithm to find (Formula presented.) • (Formula presented.) and (Formula presented.) • (Formula presented.) Further, we give an upper bound for the broadcast domination number of the modular product of two connected graphs and exact values are determined for the modular product of two graphs involving path, cycle and complete graphs. © 2022 The Author(s). Published with license by Taylor & Francis Group, LLC.
CRITICAL ASPECTS IN BROADCAST DOMINATION
(University of Zielona Gora, 2024) Sen, J.; Kola, S.R.
A dominating broadcast labeling of a graph G is a function f : V (G) → {0, 1, 2, . . . , diam(G)} such that f(v) ≤ e(v) for all v ∈ V (G) and [ v2V (G) f(v)>0 [{u ∈ V (G) : d(u, v) ≤ f(v)}] = V (G), where e(v) is the eccentricity of v. The cost of f is Σ v2V (G) f(v). The minimum of costs over all the dominating broadcast labelings of G is called the broadcast domination number γb(G) of G. In this paper, we introduce the critical aspects in broadcast domination and study it with respect to edge deletion and edge addition. A graph G is said to be k-γ+ b -edge-critical (k-γ- b - edge-critical) if γb(G - e) > γb(G), for every edge e ∈ E(G) (if γb(G + e) < γb(G), for every edge e /∈ E(G)), where γb(G) = k. We give a necessary and sufficient condition for a graph to be k-γ+ b -edge-critical. We characterize k-γ- b -edge-critical graphs for k = 1, 2, and give necessary conditions of the same for k > 3. Further, we define the broadcast bondage number and the broadcast reinforcement number of a graph, and give tight upper bounds for them. © 2024 University of Zielona Gora. All rights reserved.
Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two
(2018) Kola, S.R.; Gudla, B.; Niranjan, P.K.
An L(2,1)-coloring of a simple connected graph G is an assignment f of nonnegative integers to the vertices of G such that fu-fv2 if d(u,v)=1 and fu-fv1 if d(u,v)=2 for all u,v∈V(G), where d(u,v) denotes the distance between u and v in G. The span of f is the maximum color assigned by f. The span of a graph G, denoted by (G), is the minimum of span over all L(2,1)-colorings on G. An L(2,1)-coloring of G with span (G) is called a span coloring of G. An L(2,1)-coloring f is said to be irreducible if there exists no L(2,1)-coloring g such that g(u)f(u) for all u∈V(G) and g(v)
Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two
(Hindawi Limited, 2018) Kola, S.R.; Gudla, B.; Niranjan, P.K.
An L(2,1)-coloring of a simple connected graph G is an assignment f of nonnegative integers to the vertices of G such that fu-fv2 if d(u,v)=1 and fu-fv1 if d(u,v)=2 for all u,v∈V(G), where d(u,v) denotes the distance between u and v in G. The span of f is the maximum color assigned by f. The span of a graph G, denoted by (G), is the minimum of span over all L(2,1)-colorings on G. An L(2,1)-coloring of G with span (G) is called a span coloring of G. An L(2,1)-coloring f is said to be irreducible if there exists no L(2,1)-coloring g such that g(u)f(u) for all u∈V(G) and g(v)
The k-distance chromatic number of trees and cycles
(2019) Niranjan, P.K.; Kola, S.R.
For any positive integer k, a k-distance coloring of a graph G is a vertex coloring of G in which no two vertices at distance less than or equal to k receive the same color. The k-distance chromatic number of G, denoted by ?kG is the smallest integer ? for which G has a k-distance ?-coloring. In this paper, we improve the lower bound for the k-distance chromatic number of an arbitrary graph for k odd case and see that trees achieve this lower bound by determining the k-distance chromatic number of trees. Also, we find k-distance chromatic number of cycles and 2-distance chromatic number of a graph G in which every pair of cycles are edge disjoint. 2017 Kalasalingam University
L(2, 1)-coloring and its related problems for Mycielskians of certain classes of graphs
(World Scientific, 2025) Kola, S.R.; Gudla, B.; Niranjan, P.K.
In an L(2, 1)-coloring f of G with span k, h ?{0, 1, 2,…,k} is a hole if there is no vertex v in G such that f(v) = h. An L(2, 1)-coloring with span k is said to be a no-hole coloring if it uses all the colors from {0, 1, 2,…,k}. An L(2, 1)-coloring of a graph G is irreducible if color of no vertex can be decreased and yield another L(2, 1)-coloring of G. A graph G is inh-colorable if there exists an irreducible no-hole coloring of G. The inh-span of a graph G, denoted by ?inh(G) is the smallest number k such that there is an irreducible no-hole L(2, 1)-coloring of G with span k. The maximum number of holes in G is the maximum number of holes over all irreducible span colorings of G. In this paper, we give an algorithm to define an L(2, 1)-coloring for the Mycielskian ?(G) of an arbitrary graph G. We prove that the algorithm gives span colorings for Mycielskians of path Pn (n ? 16), cycle Cn(n ? 19), some classes of trees and concatenation of an arbitrary graph with trees. Also, we show that the Mycielskians for the above classes of graphs are inh-colorable and their inh-span is same as the ?-number. Further, we determine the maximum number of holes over all irreducible span colorings for Mycielskians of path Pn (n ? 17), cycle Cn (n ? 20), some classes of trees and concatenation of an arbitrary graph with trees. © 2025 World Scientific Publishing Company.
A lower bound for radio ?-chromatic number of an arbitrary graph
(2015) Kola, S.R.; Panigrahi, P.
Radio ?-coloring is a variation of Hale's channel assignment problem, in which one seeks to assign positive integers to the vertices of a graph G, subject to certain constraints involving the distance be- tween the vertices. Speciffically, for any simple connected graph G with diameter d and a positive integer ?, 1 ? ? ? d, a radio ?-coloring of G is an assignment f of positive integers to the vertices of G such that jf(u)-f(v)j ? 1+?-d(u; v), where u and v are any two distinct vertices of G and d(u; v) is the distance between u and v. In this paper we give a lower bound for the radio ?-chromatic number of an arbitrary graph in terms of k, the total number of vertices n and a positive integer M such that d(u; v)+d(v;w)+d(u;w) ? M for all u; v;w 2 V (G). If M is the triameter we get a better lower bound. We also ffind the triameter M for several graphs, and show that the lower bound obtained for these graphs is sharp for the case ? = d. 2015 University of Calgary.
On the Radio k-chromatic Number of Paths
(University of Salento, 2022) Niranjan, P.K.; Kola, S.R.
A radio k-coloring of a graph G is an assignment f of positive integers (colors) to the vertices of G such that for any two vertices u and v of G, the difference between their colors is at least 1 + k - d(u, v). The span rck(f) of f is (Formula Presented). The radio k-chromatic number (Formula Presented). In this paper, in an attempt to prove a conjecture on the radio k-chromatic number of path, we determine the radio k-chromatic number of paths Pn for (Formula Presented) if k is odd and (Formula Presented) if k is even. © 2022 Università del Salento
On the Radio k-chromatic Number of Some Classes of Trees
(2020) Niranjan, P.K.; Kola, S.R.
Radio k-coloring of a graph G is an assignment f of positive integers (colors) to the vertices of G such that for any two distinct vertices u and v of G, the difference between their colors is at least 1 + k- d(u, v). The span rck(f) of f is the largest number assigned by f. The radio k-chromatic number rck(G) is min{rck(f):fis a radiok-coloring ofG}. When k= diam(G) , f is called a radio coloring of G and the corresponding radio k-chromatic number is known as the radio number of G. In this paper, we determine the radio number of some classes of trees. Also, we find the radio d-chromatic number of infinitely many trees and graphs of arbitrarily large diameter constructed from trees of diameter d in some subclasses of the above classes. 2020, Springer Nature India Private Limited.
On the Radio k-chromatic Number of Some Classes of Trees
(Springer, 2020) Niranjan, P.K.; Kola, S.R.
Radio k-coloring of a graph G is an assignment f of positive integers (colors) to the vertices of G such that for any two distinct vertices u and v of G, the difference between their colors is at least 1 + k- d(u, v). The span rck(f) of f is the largest number assigned by f. The radio k-chromatic number rck(G) is min{rck(f):fis a radiok-coloring ofG}. When k= diam(G) , f is called a radio coloring of G and the corresponding radio k-chromatic number is known as the radio number of G. In this paper, we determine the radio number of some classes of trees. Also, we find the radio d-chromatic number of infinitely many trees and graphs of arbitrarily large diameter constructed from trees of diameter d in some subclasses of the above classes. © 2020, Springer Nature India Private Limited.
On the radio number for corona of paths and cycles
(2019) P.K., N.; Kola, S.R.
Radio k-coloring of graphs is one of the variations of frequency assignment problem. For a simple connected graph G and a positive integer k?diam(G), a radio k-coloring is an assignment f of positive integers (colors) to the vertices of G such that for every pair of distinct vertices u and v of G, the difference between their colors is at least 1+k?d(u,v). The maximum color assigned by f is called its span, denoted by rck(f). The radio k-chromatic number rck(G) of G is min{rck(f):fis a radiok-coloring ofG}. If d is the diameter of G, then a radio d-coloring is referred as a radio coloring and the radio d-chromatic number as the radio number, denoted by rn(G), of G. The corona G?H of two graphs G and H is the graph obtained by taking one copy of G and |V(G)| copies of H, and joining each and every vertex of the ith copy of H with the ith vertex of G by an edge. In this paper, for path Pn and cycle Cm, m?5, we determine rn(Pn?Cm) when n is even, and give an upper bound for the same when n is odd. Also, for m?4, we determine the radio number of Pn?Pm when n is even, and give both upper and lower bounds for rn(Pn?Pm) when n is odd. 2019 Kalasalingam University
On the radio number for corona of paths and cycles
(Taylor and Francis Ltd., 2020) Niranjan, P.K.; Kola, S.R.
Radio (Formula presented.) -coloring of graphs is one of the variations of frequency assignment problem. For a simple connected graph (Formula presented.) and a positive integer (Formula presented.), a radio (Formula presented.) -coloring is an assignment (Formula presented.) of positive integers (colors) to the vertices of (Formula presented.) such that for every pair of distinct vertices (Formula presented.) and (Formula presented.) of (Formula presented.), the difference between their colors is at least (Formula presented.). The maximum color assigned by (Formula presented.) is called its span, denoted by (Formula presented.). The radio (Formula presented.) -chromatic number (Formula presented.) of (Formula presented.) is (Formula presented.). If (Formula presented.) is the diameter of (Formula presented.), then a radio (Formula presented.) -coloring is referred as a radio coloring and the radio (Formula presented.) -chromatic number as the radio number, denoted by (Formula presented.), of (Formula presented.). The corona (Formula presented.) of two graphs (Formula presented.) and (Formula presented.) is the graph obtained by taking one copy of (Formula presented.) and (Formula presented.) copies of (Formula presented.), and joining each and every vertex of the (Formula presented.) copy of (Formula presented.) with the (Formula presented.) vertex of (Formula presented.) by an edge. In this paper, for path (Formula presented.) and cycle (Formula presented.), (Formula presented.), we determine (Formula presented.) when (Formula presented.) is even, and give an upper bound for the same when (Formula presented.) is odd. Also, for (Formula presented.), we determine the radio number of (Formula presented.) when (Formula presented.) is even, and give both upper and lower bounds for (Formula presented.) when (Formula presented.) is odd. © 2018 Kalasalingam University. Published with license by Taylor & Francis Group, LLC.
Radio Numbers of Some Caterpillars
(2015) Kola, S.R.; Panigrahi, P.
Radio coloring of a graph G with diameter d is an assignment f of positive integers to the vertices of G such that |f(u)-f(v)|?1+d-d(u,v) where u and v are any two distinct vertices of G and d(u,v) is the distance between u and v. The number max {f(u): u? V(G)} is called the span of f. The minimum of spans over all radio colorings of G is called the radio number of G, denoted by rn(G). An m-distant tree T is a tree in which there is a path P of maximum length such that every vertex in V(T) \ V(P) is at most distance m from P. This path P is called a central path. Every tree can be represented as an m-distant tree for some non-negative integer m. In this paper, we find the radio number of a class of 1-distant trees (or caterpillars). 2015 Elsevier B.V.
Radio Numbers of Some Caterpillars
(Elsevier B.V., 2015) Kola, S.R.; Panigrahi, P.
Radio coloring of a graph G with diameter d is an assignment f of positive integers to the vertices of G such that |f(u)-f(v)|?1+d-d(u,v) where u and v are any two distinct vertices of G and d(u,v) is the distance between u and v. The number max {f(u): u? V(G)} is called the span of f. The minimum of spans over all radio colorings of G is called the radio number of G, denoted by rn(G). An m-distant tree T is a tree in which there is a path P of maximum length such that every vertex in V(T) \ V(P) is at most distance m from P. This path P is called a central path. Every tree can be represented as an m-distant tree for some non-negative integer m. In this paper, we find the radio number of a class of 1-distant trees (or caterpillars). © 2015 Elsevier B.V.
Some classes of trees with maximum number of holes two
(2018) Kola, S.R.; Gudla, B.; Niranjan, P.K.
An L2,1-coloring of a simple connected graph G is an assignment of non-negative integers to the vertices of G such that adjacent vertices color difference is at least two, and vertices that are at distance two from each other get different colors. The maximum color assigned in an L2,1-coloring is called span of that coloring. The span of a graph G denoted by ?G is the smallest span taken over all L2,1-colorings of G. A hole is an unused color within the range of colors used by the coloring. An L2,1-coloring f is said to be irreducible if no other L2,1-coloring can be produced by decreasing a color of f. The maximum number of holes of a graph G, denoted by H?G, is the maximum number of holes taken over all irreducible L2,1-colorings with span ?G. Laskar and Eyabi (Christpher, 2009) conjectured that if T is a tree, then H?T=2 if and only if T=Pn, n>4. We show that this conjecture does not hold by providing a counterexample. Also, we give some classes of trees with maximum number of holes two. 2018 Kalasalingam University
Some classes of trees with maximum number of holes two
(Taylor and Francis Ltd., 2020) Kola, S.R.; Gudla, B.; Niranjan, P.K.
An (Formula presented.) -coloring of a simple connected graph (Formula presented.) is an assignment of non-negative integers to the vertices of (Formula presented.) such that adjacent vertices color difference is at least two, and vertices that are at distance two from each other get different colors. The maximum color assigned in an (Formula presented.) -coloring is called span of that coloring. The span of a graph (Formula presented.) denoted by (Formula presented.) is the smallest span taken over all (Formula presented.) -colorings of (Formula presented.). A hole is an unused color within the range of colors used by the coloring. An (Formula presented.) -coloring (Formula presented.) is said to be irreducible if no other (Formula presented.) -coloring can be produced by decreasing a color of (Formula presented.). The maximum number of holes of a graph (Formula presented.), denoted by (Formula presented.), is the maximum number of holes taken over all irreducible (Formula presented.) -colorings with span (Formula presented.). Laskar and Eyabi (Christpher, 2009) conjectured that if (Formula presented.) is a tree, then (Formula presented.) if and only if (Formula presented.), (Formula presented.). We show that this conjecture does not hold by providing a counterexample. Also, we give some classes of trees with maximum number of holes two. © 2018 Kalasalingam University. Published with license by Taylor & Francis Group, LLC.
The k-distance chromatic number of trees and cycles
(Kalasalingam University info@kalasalingam.ac.in, 2019) Niranjan, P.K.; Kola, S.R.
For any positive integer k, a k-distance coloring of a graph G is a vertex coloring of G in which no two vertices at distance less than or equal to k receive the same color. The k-distance chromatic number of G, denoted by ?kG is the smallest integer ? for which G has a k-distance ?-coloring. In this paper, we improve the lower bound for the k-distance chromatic number of an arbitrary graph for k odd case and see that trees achieve this lower bound by determining the k-distance chromatic number of trees. Also, we find k-distance chromatic number of cycles and 2-distance chromatic number of a graph G in which every pair of cycles are edge disjoint. © 2017 Kalasalingam University
The radio k -chromatic number for corona of graphs
(World Scientific, 2023) Niranjan, P.K.; Kola, S.R.
For a connected simple graph G and a positive integer k ≤diam(G), a radio k-coloring is an assignment f of positive integers (colors) to the vertices of G such that for every pair of distinct vertices u and v in G, |f(u) - f(v)|≥ 1 + k - d(u,v). The span rck(f) of f is maxvϵV(G)f(v). The minimum of {rck(f): f is a radio k-coloring of G} is called the radio k-chromatic number of G and is denoted by rck(G). If d is the diameter of G, then a radio d-coloring is referred as a radio coloring and the radio d-chromatic number as the radio number, rn(G), of G. In this paper, we obtain an upper bound for the radio k-chromatic number of the corona of two graphs G and H for k ≥ 2, and we obtain a necessary condition for this upper bound to be exact. Also, we see that for path Pm, m even and complete graph Kn the upper bound is sharp for rck(Kn - H) and rn(Pm - H), where H is an arbitrary graph. Further, we give a lower bound and an improved upper bound for rn(Pm - H), m odd and rn(Qn - H), Qn is hypercube. © 2023 World Scientific Publishing Company.