Search

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. It is known that the decision problems for Italian domination number γ I (G) , 2 -rainbow domination number γ r 2 (G) and Roman domination number γ R (G) are NP-complete. Recently, it was proved that γ I (M (G)) = γ r 2 (M (G)) = γ R (M (G)) = n for a graph G of order n. In this paper, we continue to study several domination and domatic numbers in middle graphs. We also obtain closed formulas for domination, secure domination and total domination numbers in middle graphs of rooted product graphs. [ABSTRACT FROM AUTHOR]

A double Italian dominating (DID) function of a graph G = (V, E) is a function f : V (G) → {0, 1, 2, 3} having the property that for every vertex v ∈ V, Pu∈NG[v] f(u) ≥ 3, if f(v) ∈ {0, 1}. A restrained double Italian dominating (RDID) function is a DID function f such that the subgraph induced by the vertices with label 0 has no isolated vertex. A total restrained double Italian dominating (TRDID) function is an RDID function f such that the set {v ∈ V : f(v) > 0} induces a subgraph with no isolated vertex. We initiate the study of TRDID function of any graph G. The TRDID and RDID functions of the middle of any graph G are investigated, and then, the sharp bounds for these parameters are established. Finally, for a graph H, we provide the minimum value of TRDID and RDID functions for corona graphs, H ◦ K1, H ◦ K2 and middle of them. [ABSTRACT FROM AUTHOR]

Given a graph G, we consider the Italian domination number γI(G), the 2-rainbow domination number γr2(G) and the Roman domination number γR(G). It is known that γI(G) ≤ γr2(G) ≤ γR(G) holds for any graph G. In this paper, we prove that γI(M(G)) = γr2(M(G)) = γR(M(G)) = n for the middle graph M(G) of a graph G of order n, which gives an answer for an open problem posed by Chellali et al. [Discrete Appl. Math. 204 (2016) 22–28]. Moreover, we give a complete characterization of Roman domination stable middle graphs, 2-rainbow domination stable middle graphs and Italian domination stable middle graphs. [ABSTRACT FROM AUTHOR]

An Italian dominating function on a graph G = (V , E) is defined as a function f : V → { 0 , 1 , 2 } satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2 or at least two vertices x , y for which f (x) = f (y) = 1. The weight of an Italian dominating function is w (f) = Σ v ∈ V f (v). The Italian domination number is the minimum weight taken over all Italian dominating functions of G and denoted by γ I (G). Three domination parameters related to the Italian dominating function are total Italian, restrained Italian, and total restrained Italian dominating function. A total ((restrained) (total restrained)) Italian dominating function f is an Italian dominating function if the set of vertices with positive label ((the set of vertices with label 0), (at the same time, the set of vertices with positive label and the set of vertices with label 0)) induces ((induces) (induce)) a subgraph with no isolated vertex. A minimum weight of any total ((restrained) (total restrained)) Italian dominating function f is called a total ((restrained) (total restrained)) Italian domination number denoted by γ tI (G) , (( γ rI (G)) ( γ trI (G))). We initiate the study of parameters, restrained and total restrained Italian domination number of a graph G and the middle graph of G. For the family of standard graphs, we obtain the exact value of these parameters. For arbitrary graph G , we obtain the sharp bounds of these parameters, and for some corona graphs, we establish the precise value of these parameters. [ABSTRACT FROM AUTHOR]

Topological index is sometimes also known as graph theoretic index, is a numerical invariant of a graph, the topological indices are classified on degree and distance based concepts. The status σ(u) of a vertex u ∈ V (G) is defined as the sum of its distances between each other vertex in V(G) of the graph G. Ramane and Yalnaik defined the distance based topological indices such as first and second status connectivity indices. In this article bounds for the first and second status connectivity indices of middle graph of a graph are established and further status connectivity indices of middle graph of certain graphs are computed.

Let G be a graph and let S(G), M(G), and T(G) be the subdivision, the middle, and the total graph of G, respectively. Let dim(G), edim(G), and mdim(G) be the metric dimension, the edge metric dimension, and the mixed metric dimension of G, respectively. In this paper, for the subdivision graph it is proved that 1 2 max{dim(G), edim(G)} ≤ mdim(S(G)) ≤ mdim(G). A family of graphs Gn is constructed for which mdim(Gn) − mdim(S(Gn)) ≥ 2 holds and this shows that the inequality mdim(S(G)) ≤ mdim(G) can be strict, while for a cactus graph G, mdim(S(G)) = mdim(G). For the middle graph it is proved that dim(M(G)) ≤ mdim(G) holds, and if G is tree with n1(G) leaves, then dim(M(G)) = mdim(G) = n1(G). Moreover, for the total graph it is proved that mdim(T (G)) = 2n1(G) and dim(G) ≤ dim(T (G)) ≤ n1(G) hold when G is a tree. [ABSTRACT FROM AUTHOR]

In this paper, we study the domination number of middle graphs. Indeed, we obtain tight bounds for this number in terms of the order of the graph G. We also compute the domination number of some families of graphs such as star graphs, double start graphs, path graphs, cycle graphs, wheel graphs, complete graphs, complete bipartite graphs and friendship graphs, explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the domination number of middle graphs.

Let G be a nontrivial connected graph and let c : V (G) → ℕ be a vertex coloring of G , where adjacent vertices may have the same color. For a vertex v of G , the color sum σ (v) of v is the sum of the colors of the vertices adjacent to v. The coloring c is said to be a sigma coloring of G if σ (u) ≠ σ (v) whenever u and v are adjacent vertices in G. The minimum number of colors that can be used in a sigma coloring of G is called the sigma chromatic number of G and is denoted by σ (G). In this study, we show that the sigma chromatic number of the middle graph of full binary trees of height h is 2. We also determine a lower bound for the sigma chromatic number of graphs containing an induced subgraph isomorphic to a complete graph joined by pendant vertices. With this lower bound, we obtain the sigma chromatic number of the middle graph of the graphs G n , t , cor (K n) , stars, bistars, and the middle graph of some families of trees of height 2. [ABSTRACT FROM AUTHOR]

The neighborhood color set of each vertex v in a vertex-colored graph G is defined as the collection of the colors of all the neighbors of v. If there are no two adjacent vertices that have equal neighborhood color sets, then the coloring is called a set coloring of G. The set coloring problem on G refers to the problem of determining its set chromatic number, which refers to the fewest colors using which a set coloring of G may be constructed. In this work, we consider the set coloring problem on graphs obtained from applying middle graph, a unary graph operation. The middle graph of G is the graph whose vertex set is the union of V (G) and E(G) and whose edge set is {{u, uv} : u ∈ V (G) and uv ∈ E(G)} ∪ {{uv1, uv2} : uv1, uv2 ∈ E(G) and v1 ≠ = v2}. We consider the set coloring problem on the middle graph of different tree families such as brooms, double brooms and caterpillars. We construct set colorings of such graphs using algorithms or explicit formulas. By proving the optimality of these set colorings, we obtain the set chromatic number for these different graph families. [ABSTRACT FROM AUTHOR]

In this paper, we study the domination number of middle graphs. Indeed, we obtain tight bounds for this number in terms of the order of the graph G. We also compute the domination number of some families of graphs such as star graphs, double start graphs, path graphs, cycle graphs, wheel graphs, complete graphs, complete bipartite graphs and friendship graphs, explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the domination number of middle graphs. [ABSTRACT FROM AUTHOR]

Let G be a graph. Let f : V (G) → {0, 1, 2, . . ., k − 1} be a function where k ∈ N and k > 1. For each edge uv, assign the label f (uv) = ᒥ f (u) + f (v)/2 ⏋and f is called a k-total mean cordial labeling of G if |tmf (i) − tmf (j)| ≤ 1, for all i, j ∈ {0, 1, 2, . . ., k − 1}, where tmf (x) denotes the total number of vertices and edges labelled with x, x ∈ {0, 1, 2, . . ., k − 1}. A graph with admit a k-total mean cordial labeling is called k-total mean cordial graph. In this paper we investigate the 4-Total mean cordial labeling behavior of some graphs like C4 × Pn, middle graph of Pn, total graph of Pn, middle graph of Cn, total graph of Cn and kayak paddale graph. [ABSTRACT FROM AUTHOR]

In this paper, we define middle graph of semiring valued graph M(GS) and study the regularity of M(GS) where GS is the semiring valued graph (or simply S-valued graph). [ABSTRACT FROM AUTHOR]

AbstractLet [Formula: see text] be a graph of order n(G). For a subset S of V(G), the boundary of S is defined as [Formula: see text] where N(S) is the open neighborhood of S. The external private neighborhood set of v with respect to S is defined as [Formula: see text] For a subset S of V(G), the D-differential of S is defined as [Formula: see text] where [Formula: see text] In this paper, we introduce the concept of D-differential of a graph G, which is defined as [Formula: see text] We present several lower and upper bounds of D-differential of a graph. We construct a Gallai-type theorem for the D-differential [Formula: see text] and double Roman domination number [Formula: see text] which states that [Formula: see text] Thus, we can utilize a relation between D-differential and double Roman domination number. The concept of D-differential can be a framework to find double Roman domination number of graphs. Actually, we determine the double Roman domination number of middle graphs.

A total dominator coloring of a graph G is a proper coloring of G in which each vertex of the graph is adjacent to every vertex of some color class. The total dominator chromatic number of a graph is the minimum number of color classes in a total dominator coloring. In this paper, we study the total dominator coloring on middle graphs by giving several bounds for the case of general graphs and trees. Moreover, we calculate explicitly the total dominator chromatic number of the middle graph of several known families of graphs. [ABSTRACT FROM AUTHOR]

Graph labeling is a source of valuable mathematical models for an extensive range of applications in technologies (communication networks, cryptography, astronomy, data security, various coding theory problems). An edge $ \; \delta - $ graceful labeling of a graph $ G $ with $ p\; $ vertices and $ q\; $ edges, for any positive integer $ \; \delta $, is a bijective $ \; f\; $ from the set of edge $ \; E(G)\; $ to the set of positive integers $ \; \{ \delta, \; 2 \delta, \; 3 \delta, \; \cdots\; , \; q\delta\; \} $ such that all the vertex labels $ \; f^{\ast} [V(G)] $, given by: $ f^{\ast}(u) = (\sum\nolimits_{uv \in E(G)} f(uv)\; )\; mod\; (\delta \; k) $, where $ k = max (p, q) $, are pairwise distinct. In this paper, we show the existence of an edge $ \; \delta- $ graceful labeling, for any positive integer $ \; \delta $, for the following graphs: the splitting graphs of the cycle, fan, and crown, the shadow graphs of the path, cycle, and fan graph, the middle graphs and the total graphs of the path, cycle, and crown. Finally, we display the existence of an edge $ \; \delta- $ graceful labeling, for the twig and snail graphs.

In this paper, we determine the r-dynamic chromatic number of the fan graph Fm,n and determine sharp bounds of this graph invariant for four related families of graphs: The middle graph M(Fm,n), the total graph T (Fm,n), the central graph C(Fm,n) and the line graph L(Fm,n). In addition, we determine the r-dynamic chromatic number of each one of these four families of graphs in case of being m = 1.

A total coloring of a graph G is an assignment of colors to both the vertices and edges of G, such that no two adjacent or incident vertices and edges of G are assigned the same colors. In this paper, we have discussed the total coloring and total chromatic number of middle graph, total graph of twig graph and comb graph. [ABSTRACT FROM AUTHOR]

For a given graph G, the general position problem is to find the general position number of G which is the maximum number of vertices of G such that no three vertices lie on a common geodesic and is denoted by gp(G). In this paper, the general position number for Middle, Splitting and Shadow graph of path, cycle and star are computed. [ABSTRACT FROM AUTHOR]

A hub set in a graph G is a set S ⊆ V (G) such that any two vertices outside S are connected by a path whose all internal vertices are members of S. The minimum cardinality of hub set is called hub number. In this paper, we give results for the hub number of generalized middle graphs. [ABSTRACT FROM AUTHOR]

A total dominating set of a graph G with no isolated vertices is a subset S of the vertex set such that every vertex of G is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we study the total domination number of middle graphs. Indeed, we obtain tight bounds for this number in terms of the order of the graph G. We also compute the total domination number of the middle graph of some known families of graphs explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the total domination number of middle graphs. [ABSTRACT FROM AUTHOR]

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 γ ⋆ (G) of G is defined by the domination number γ (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 β 2 (G). These parameters are incomparable in general. However, we show that γ ⋆ (T) ≤ β 2 (T) for any tree T. We also characterize all trees attaining the equality. [ABSTRACT FROM AUTHOR]

Let G be a finite simple graph with vertex set V(G) and edge set E(G). A function f : V(G) → P({1,2,...,k}) is a k-rainbow dominating function on G if for each vertex v∈V(G) for which f(v) = ∅, it holds that ⋃u∈N(v)f(u) = {1,2,...,k}. The weight of a k-rainbow dominating function is the value ∑v∈V(G)|f(v)|. The k-rainbow domination number γrk (G) is the minimum weight of a k-rainbow dominating function on G. In this paper, we initiate the study of k-rainbow domination numbers in middle graphs. We define the concept of a middle k-rainbow dominating function, obtain some bounds related to it and determine the middle 3-rainbow domination number of some classes of graphs. We also provide upper and lower bounds for the middle 3-rainbow domination number of trees in terms of the matching number. In addition, we determine the 3-rainbow domatic number for the middle graph of paths and cycles. [ABSTRACT FROM AUTHOR]

Adjacent vertex-distinguishing proper edge-coloring is the minimum number of colors required for the proper edge-coloring of [Formula: see text] in which no two adjacent vertices are incident to edges colored with the same set of colors. The minimum number of colors required for an adjacent vertex-distinguishing proper edge-coloring of [Formula: see text] is called the adjacent vertex-distinguishing proper edge-chromatic index. Adjacent vertex-distinguishing proper edge-chromatic indices of the middle graph, splitting graph and shadow graph of path and cycle are determined. Adjacent vertex-distinguishing proper edge-chromatic indices of the triangular grid [Formula: see text], [Formula: see text]-graph and generalized [Formula: see text]-graph are also determined.

An acyclic coloring is a proper vertex coloring in which no cycle in the graph is bichromatic or the subgraph induced by any two colors is acyclic. The acyclic chromatic number a(G) of a graph G is the least number of colors in an acyclic coloring of G. In this paper, acyclic coloring of middle and central graph of some graphs are investigated. For any graph G, a relation between the acyclic chromatic number and acyclic chromatic index of its line graph is derived, and using this relation, acyclic chromatic index of line graph of n -dimensional graphs like hypercube, mesh and torus are analyzed. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with n vertices and m edges, and L (G) and M (G) be the line graph and middle graph of G , respectively. Ciucu et al. (2012) [2] and Dong et al. (2013) [3] proved independently that if m is even and the maximum degree Δ (G) of G satisfies Δ (G) ≤ 3 , then L (G) has 2 m − n + 1 perfect matchings. Recently, Li et al. (2023) [6] showed that if G is a connected cubic graph and m is even, then the number of perfect matchings of M (G) equals 2 n 2 + 1 3 n 4 . In this paper, we extend the results above and show that if G is a connected graph with △ (G) ≤ 4 and m + n is even, then the number of perfect matchings of M (G) equals 2 m − n + 1 3 m − n 2 . [ABSTRACT FROM AUTHOR]

For a connected graph G, let diam(G) and d(u, v) denote the diameter of G and distance between u and v, respectively. A radio labeling of a graph G is a mapping f : V(G) Æ {0, 1, 2, ... } such that |f(u) – f(v)| ≥ diam (G) + 1 – d(u, v) for every pair of distinct vertices u, v of G. The span of f is defined as span (f) = max { f(u) – f (v) : u, v ϵ V(G)}. The radio number rn(G) of G is defined as rn(G) = min{span(f) : f is a radio labeling of G}. In this paper, we determine the radio number for middle graph of dandelion, which generalized Bantva's results (Electronic Notes in Discrete Mathematics, 63 (2017), 93-100). [ABSTRACT FROM AUTHOR]

A proper vertex colouring of a graph G is called a star colouring if every path of $G$ on four vertices is not 2-coloured. The star chromatic number is the minimum number of colours required to star colour $G$ and it is denoted by χs(G). The Star Chromatic Number of the Middle Graphs of path (Pn) Shadow Graphs of path (Pn) and Tadpole graphs (T3,n) m-fold Triangular Snake graphs (S(C3,m,n)) have been discussed in this paper. [ABSTRACT FROM AUTHOR]

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that/c(N(v))l > min (r, d(v)}, for each v £ V (G). The r-dynamic chromatic number of a graph G is the minimum k such that G has an r-dynamic coloring with k colors. In this paper, we obtain the r--dynamic chromatic number of the middle, central and line graphs of the gear graph. [ABSTRACT FROM AUTHOR]

An r-dynamic proper k-coloring of a graph G is a proper k-coloring of G such that every vertex in V (G) has neighbors in atleast min fr; d(v)g different color classes. The r-dynamic chromatic number of a graph G is the minimum k such that G has an r-dynamic coloring with k colors. In this paper we investigate the r-dynamic chromatic number for the Central graph, Middle graph, Total graph and Line graph of Double star graph. [ABSTRACT FROM AUTHOR]

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by atmost one. The notion of equitable coloring was introduced by Meyer in 1973. A proper h-colorable graph K is said to be equitably h-colorable if the vertex sets of K can be partioned into h independent color classes V1, V2, ..., Vh such that the condition ||Vi| - |Vj|| ≤ 1 holds for all different pairs of i and j and the least integer h is known as equitable chromatic number of K. In this paper, we find the equitable coloring of book graph, middle, line and central graphs of book graph. [ABSTRACT FROM AUTHOR]

In this paper, we acquired the irregular chromatic number for the following graphs: M(fn), T(fn), C(fn), L(fn), M(DFn), T(DFn), L(DFn), C(DFn), M(SFn), T(SFn), L(SFn), C(SFn). [ABSTRACT FROM AUTHOR]

In this communication, the pathos vertex semi-middle graph of a tree is introduced. Its study is concentrated only on trees. We present a characterization of those graphs whose pathos vertex semi-middle graph of a tree is planar, crossing number one and crossing number two. Also we establish a characterization of graphs whose pathos vertex semi-middle graph of a tree is noneulerian, hamiltonian. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the irregular chromatic number for the middle, total, central and line graph of triple star graph. [ABSTRACT FROM AUTHOR]

The packing chromatic number χp of a graph G is the smallest integer k for which there exists a mapping π: V(G) → {1, 2 ... , k} such that any two vertices of color i are at distance at least i + 1. In this paper, we give the packing chromatic number for the middle graph, total graph, central graph and line graph of helm graph and closed helm graph. [ABSTRACT FROM AUTHOR]

An irregular coloring is a proper coloring in which distinct vertices have different color codes. In this paper, we obtain the irregular chromatic number for middle graph, total graph, central graph and line graph of wheel graph, helm graph, gear graph and closed helm graph. [ABSTRACT FROM AUTHOR]

Graph coloring is a special case of graph labeling. Proper vertex k-coloring of a graph Gis to color all the vertices of a graph with different colors in such a way that no two adjacent vertices are assigned with the same color. In a vertex coloring of G, the set of vertices with the same color is called color class. An equitable k-coloring of a graph G is a proper k-coloring in which any two color classes differ in size by atmost one. In this paper we give results regarding the equitable coloring of central, middle, total and line graphs of Tadpole graph which is obtained by connecting a cycle graph and a path graph with a bridge. [ABSTRACT FROM AUTHOR]

A vertex magic total labeling is a bijection from the union of the vertex set and edge set to the consecutive integers 1,2,3,....,v+e with the property that for every u in the vertex set, the sum of the label of u and the label of the edges incident with u is equal to k, for some constant k. In this paper, we establish the vertex magic labeling of some classes of graphs and provide some open problems related to it. [ABSTRACT FROM AUTHOR]

Graph coloring is a special case of graph labeling. Proper vertex k-coloring of a graph Gis to color all the vertices of a graph with different colors in such a way that no two adjacent vertices are assigned with the same color. In a vertex coloring of G, the set of vertices with the same color is called color class. An equitable k-coloring of a graph G is a proper k-coloring in which any two color classes differ in size by atmost one. In this paper we give results regarding the equitable coloring of central, middle, total and line graphs of Tadpole graph which is obtained by connecting a cycle graph and a path graph with a bridge. [ABSTRACT FROM AUTHOR]

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that |c(N(v))| ≥ min {r, d(v)}, for each v ∈ V (G). The r-dynamic chromatic number of a graph G is the minimum k such that G has an r-dynamic coloring with k colors. In this paper, we obtain the δ-dynamic chromatic number of middle, total, central and line graph of double wheel graph (r = δ). [ABSTRACT FROM AUTHOR]

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such...The r-dynamic chromatic number of a graph G is the minimum k such that G has an r-dynamic coloring with k colors. In this paper we investigate the r-dynamic chromatic number of the central graph, middle graph, total graph and line graph of the triple star graph K1,n,n,n denoted by C(K1,n,n,n), M(K1,n,n,n), T(K1,n,n,n) and L(K1,n,n,n) respectively. [ABSTRACT FROM AUTHOR]

An equitable k-coloring of a graph G is a proper k-coloring of G such that the sizes of any two color class differ by at most one. In this paper we investigate the equitable chromatic number for the Central graph, Middle graph, Total graph and Line graph of Triple star graph K1,n,n,n denoted by C(K1,n,n,n), M(K1,n,n,n), T(K1,n,n,n) and L(K1,n,n,n) respectively. [ABSTRACT FROM AUTHOR]

A set is a -point set dominating set (2-psd set) of a graph if for any subset , there exists a nonempty subset containing at most two vertices such that the subgraph induced by is connected. The -point set domination number of , denoted by , is the minimum cardinality of a 2-psd set of . In this paper, we determine the lower bounds and an upper bound on of a graph. We also characterize extremal graphs for the lower bounds and identify some well-known classes of both separable and nonseparable graphs attaining the upper bound. [ABSTRACT FROM AUTHOR]

Erratum Identification and corrections of the existing mistakes in the paper On the total graph of Mycielski graphs, central graphs and their covering numbers, Discuss. Math. Graph Theory 33 (2013) 361-371.