Search

The harmonic index of a graph Gis defined as the sum of weights 2di+djover all edges vivjof G, where diand djare the degrees of the vertices viand vjin G, respectively. In this paper we resolve a conjecture, obtained by the AutoGraphiX system, about the relation between the harmonic index and the algebraic connectivity of graphs.

AbstractFor an integer k≥1,an independent k-rainbow dominating function (IkRDF for short) on a graph Gis a function gthat assigns to each vertex a set of colors chosen from the subsets of {1,2,…,k}satisfying the following conditions: (i) if g(v)=∅, then ∪u∈N(v)g(u)={1,…,k}, and (ii) the set S={v|g(v)≠∅}is an independent set. The weight of an IkRDF gis the value w(g)=∑v∈V(G)|f(v)|. The independent k-rainbow domination number irk(G)is the minimum weight of an IkRDF on G. In this paper, we initiate a study of the independent k-rainbow bondage number birk(G)of a graph Ghaving at least one component of order at least three, defined as the smallest size of set of edges F⊆E(G)for which irk(G−F)>irk(G). We begin by showing that the decision problem associated with the independent k-rainbow bondage problem is NP-hard for general graphs for k≥2. Then various upper bounds on bir2(G)are established as well as exact values on it for some special graphs. In particular, for trees Tof order at least three, it is shown that bir2(T)≤2.

AbstractFor an integer k≥1,let fbe a function that assigns labels from the set {0,1,…,k+1}to the vertices of a simple graph G=(V,E). The active neighborhood AN(v) of a vertex v∈V(G)with respect to fis the set of all neighbors of vthat are assigned non-zero values under f. A [k]-Roman dominating function ([k]-RDF) is a function f:V(G)→{0,1,2,…,k+1}such that for every vertex v∈V(G)with f(v) < k, we have ∑u∈N[v]f(u)≥|AN(v)|+k. The weight of a [k]-RDF is the sum of its function values over the whole set of vertices, and the [k]-Roman domination number γ[kR](G)is the minimum weight of a [k]-RDF on G. In this paper we determine various bounds on the [k]-Roman domination number. In particular, we show that for any integer k≥2every connected graph Gof order n≥3, satisfies γ[kR](G)≤(2k+1)4n,and we characterize the graphs Gattaining this bound. Moreover, we show that if Tis a nontrivial tree, then γ[kR](T)≥kγ(T)+1for every integer k≥2and we characterize the trees attaining the lower bound. Finally, we prove the NP-completeness of the [k]-Roman domination problem in bipartite and chordal graphs.

AbstractA restrained Italian dominating function (RID-function) on a graph G=(V,E)is a function f:V→{0,1,2}satisfying: (i) f(N(u))≥2for every vertex u∈V(G)with f(u)=0, where N(u)is the set of vertices adjacent to u; (ii) the subgraph induced by the vertices assigned 0 under fhas no isolated vertices. The weight of an RID-function is the sum of its function value over the whole set of vertices, and the restrained Italian domination number is the minimum weight of an RID-function on G. In this paper, we initiate the study of the restrained Italian reinforcement number rrI(G)of a graph Gdefined as the cardinality of a smallest set of edges that we must add to the graph to decrease its restrained Italian domination number. We begin by showing that the decision problem associated with the restrained Italian reinforcement problem is NP-hard for arbitrary graphs. Then several properties as well as some sharp bounds of the restrained Italian reinforcement number are presented.

AbstractIn this article, we initiate a study of hop total Roman domination defined as follows: a hop total Roman dominating function(HTRDF) on a graph is a function such that for every vertex uwith f(u) = 0 there exists a vertex vat distance 2 from uwith f(v) = 2 and the subgraph induced by the vertices assigned non-zero values under fhas no isolated vertices. The weight of an HTRDF is the sum of its function values over all vertices, and the hop total Roman domination number equals the minimum weight of an HTRDF on G. We provide several properties on the hop total Roman domination number. More precisely, we show that the decision problem corresponding to the hop total Roman domination problem is NP-complete for bipartite graphs, and we determine the exact value of for paths and cycles. Moreover, we characterize all connected graphs Gof order nwith Finally, we show that for every tree Tof diameter at least 3, where is the hop total domination number.

For a connected graph G, let γ(G)and γc(G)denote the domination number and the connected domination number, respectively. Let Hbe a graph obtained from a triangle abcby adding a pendant edge at aand a pendant path of length 3 at each of band c. In 2014, Camby and Schaudt conjectured that for any connected {P9,C9,H}-free graph G, γc(G)≤2γ(G). In this paper, we settle the conjecture in the affirmative.

AbstractLet be an integer and Ga simple graph with vertex set V(G). Let fbe a function that assigns labels from the set to the vertices of G. For a vertex the active neighbourhood AN(v) of vis the set of all vertices wadjacent to vsuch that A [k]-Roman dominating function (or [k]-RDF for short) is a function satisfying the condition that for any vertex with f(v) < k, The weight of a [k]-RDF is and the [k]-Roman domination number of Gis the minimum weight of an [k]-RDF on G. In this paper we shall be interested in the study of the [k]-Roman domination subdivision number sdof Gdefined as the minimum number of edges that must be subdivided, each once, in order to increase the [k]-Roman domination number. We first show that the decision problem associated with sdis NP-hard. Then various properties and bounds are established.

AbstractA double Roman dominating function (DRDF) on a graph is a function such that every vertex uwith f(u) = 0 is adjacent to at least one vertex assigned a 3 or to at least two vertices assigned a 2, and every vertex vwith f(v) = 1 is adjacent to at least one vertex assigned 2 or 3. The weight of a DRDF is the sum of its function values over all vertices. A DRDF fis an independent double Roman dominating function (IDRDF) if the set of vertices assigned 1, 2 and 3 is independent. The independent double Roman domination number is the minimum weight over all IDRDFs of G. Every graph Gsatisfies where i(G) is the independent domination number. In this paper, we give a characterization of all trees Twith

AbstractThe sum-connectivity index of a graph Gis defined as the sum of weights over all edges uvof G, where duand dvare the degrees of the vertices uand vin G, respectively. The sum-connectivity index is one of the most important indices in chemical and mathematical fields. The spectral radius of a square matrix Mis the maximum among the absolute values of the eigenvalues of M. Let q(G) be the spectral radius of the signless Laplacian matrix where D(G) is the diagonal matrix having degrees of the vertices on the main diagonal and A(G) is the (0, 1) adjacency matrix of G. The sum-connectivity index of a graph Gand the spectral radius of the matrix Q(G) have been extensively studied. We investigate the relationship between the sum-connectivity index of a graph Gand the spectral radius of the matrix Q(G). We prove that for some connected graphs with nvertices and medges,

AbstractFor a graph an independent double Roman dominating function (IDRDF) is a function having the property that: (i) every vertex with f(v) = 0 has a neighbor uwith f(u) = 3 or at least two neighbors xand ysuch that (ii) every vertex with f(v) = 1 has at least one neighbor assigned a 2 or 3 under f; (iii) the set of vertices assigned non-zero values under fis independent. The weight of an IDRDF is the sum of its values overs all vertices, and the independent double Roman domination number is the minimum weight of an IDRDF on In this article, we show that for every tree Tof order where s(T) is the number of support vertices of T, improving the -upper bound established in [Maimani et al. Independent double Roman domination in graphs, Bulletin of the Iranian Mathematical Society, 46 (2020) 543–555]. Moreover, we characterize the trees Tof order with

AbstractLet be the total domination number and let be the total domination subdivision number of a graph Gwith no isolated vertex. In this paper, we show that for some classes of graphs G, which partially solve the conjecture presented by Favaron et al.

A Roman dominating functionon a graph Gis a function f:V(G)?{0,1,2}satisfying the condition that every vertex ufor which f(u)=0is adjacent to at least one vertex vfor which f(v)=2. A Roman dominating function fis called a restrained Roman dominating functionif the induced subgraph of Gby the vertices with label 0 has no isolated vertex. The weight of a restrained Roman dominating function is the value ?(f)=?u?V(G)f(u). The minimum weight of a restrained Roman dominating function of Gis called the restrained Roman domination numberof Gand denoted by ?rR(G). In this paper, we show that for any graph Gof order n=5, 6=?rR(G)+?rR(G¯)=n+5and characterize all the extremal graphs. In addition, we classify all graphs with large restrained Roman domination number.

AbstractIn this work, we continue to survey what has been done on the Roman domination. More precisely, we will present in two sections several variations of Roman dominating functions as well as the signed version of some of these functions. It should be noted that a first part of this survey comprising 9 varieties is published as a chapter book in “Topics in domination in graphs” edited by T.W. Haynes, S.T. Hedetniemi and M.A. Henning. We recall that a function is a Roman dominating function (or just RDF) if every vertex ufor which f(u) = 0 is adjacent to at least one vertex vfor which f(v) = 2. The Roman domination number of a graph G, denoted by is the minimum weight of an RDF on G.

AbstractFor a graph G= (V,E), a double Roman dominating function has the property that for every vertex with f(v) = 0, either there exists a vertex , with f(u) = 3, or at least two neighbors having f(x) = f(y) = 2, and every vertex with value 1 under fhas at least a neighbor with value 2 or 3. The weight of a DRDFis the sum . A DRDF fis called independent if the set of vertices with positive weight under f, is an independent set. The independent double Roman domination number is the minimum weight of an independent double Roman dominating function on G. In this paper, we show that for every graph Gof order n, and , where and i(G) are the independent 3-rainbow domination, independent Roman domination and independent domination numbers, respectively. Moreover, we prove that for any tree G, .

AbstractA double Roman dominating function (DRDF) on a graph G= (V, E) is a function f: V(G) → {0, 1, 2, 3} having the property that if f(v) = 0, then vertex vmust have at least two neighbors assigned 2 under for one neighbor wwith f(w) = 3, and if f(v) = 1, then vertex vmust have at least one neighbor wwith f(w) ≥ 2. A DRDF fis called a global double Roman dominating function(GDRDF) if fis also a DRDF of the complement of G. The weight of a GDRDF is the sum of its function value over all vertices. The global double Roman domination number of G, denoted by γgdR(G), is the minimum weight of a GDRDF on G. In this paper, we initiate the study of the global double Roman domination number. We obtain some properties of global double Roman domination number.

ABSTRACTLet kbe a positive integer, and set . Let Gbe a graph. A k-rainbow dominating function(or k-RDF) of Gis a function ffrom to such that for a vertex with , the condition is fulfilled, where is the open neighbourhood of v. The weightof k-RDF fof Gis the value . The k-rainbow domination numberof G, denoted by , is the minimum weight of a k-RDF of G. We focus on two results (here denote the maximum degree of G): (i) If a graph Gsatisfies , then (proved in Z. Shao, M. Liang, C. Yin, X. Xu, P. Pavlič, and J. Žerovnik, On rainbow domination numbers of graphs, Inform. Sci. 254 (2014), pp. 225–234). (ii) For any graphs G, (proved in D. Meierling, S.M. Sheikholeslami, and L. Volkmann, Nordhaus–Gaddum bounds on the k-rainbow domatic number of a graph, Appl. Math. Lett. 24 (2011), pp. 1758–1761). In this paper, we give a common improvement of (i) and (ii) for the case where , and prove that . Moreover, by partially using the above result, we also obtain a Nordhaus–Gaddum inequality for the k-rainbow domination number and the k-rainbow domination number of ladders.

The game domination number of a (simple, undirected) graph is defined by the following game. Two players, \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{A}}$\end{document}and \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{D}}$\end{document}, orient the edges of the graph alternately until all edges are oriented. Player \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{D}}$\end{document}starts the game, and his goal is to decrease the domination number of the resulting digraph, while \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{A}}$\end{document}is trying to increase it. The game domination number of the graph G, denoted by γg(G), is the domination number of the directed graph resulting from this game. This is well defined if we suppose that both players follow their optimal strategies. Alon et al. (Discrete Math 256 (2002), 23–33) conjectured that, if both Gand \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}$\overline{G}$\end{document}are connected graphs with nvertices, then \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}$\gamma_{g}(G)+\gamma_{g}(\overline{G})\le\frac{2}{3}{n}+{3}$\end{document}. In this paper we prove that this conjecture is true for n⩾41. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 323–329, 2010

AbstractLet G= (V, E) be a graph of order nand size m. The open neighborhood N(v) of a vertex v∈ Vis the set of all vertices adjacent to v. Its closed neighborhood is N[v] = N(v) ∪ {v}. A signed (total) dominating function on G, is a function f: V→ {−1, 1} such that ∑x∈N[v]f(x) ≥ 1 (∑x∈N(v)f(x) ≥ 1) for each v∈ V. The weight of a signed (total) dominating function fis ω(f) = ∑v∈Vf(v). The minimum weight taken over all signed (total) dominating function fof G, denoted by γs(G)(γst(G)), is called the signed (total) domination number of G. In the paper, we give bounds on the Laplacian spectrum of Ginvolving the signed domination and signed total domination numbers.

We study here the Cabibbo enhanced charmed baryon decays in theSU(4) semidynamical model. The weak Hamiltonian 20″ + 15 + 45 + 45* can have the parity violating amplitude for charmed baryon decays. Decay width and α for some modes are also calculated.