Search

The Sombor index of the graph G is a degree based topological index, deffned as SO =P uv2E(G) p dG(u)2 + dG(v)2, where dG(u) is the degree of the vertex u of G and E(G) is the edge set of G. In this paper we calculate SO of some graph transformations. [ABSTRACT FROM AUTHOR]

For a graph G with no isolated vertex, a covering total double Roman dominating function (CTDRD function) f of G is a total double Roman dominating function (TDRD function) of G for which the set fv 2 V (G)jf(v) 6= 0g is a vertex cover set. The covering total double Roman domination number ctdR(G) equals the minimum weight of an CTDRD function on G. An CTDRD function on G with weight ctdR(G) is called a ctdR(G)-function. In this paper, the graphs G with small ctdR(G) are characterised. We show that the decision problem associated with CTDRD is NP-complete even when restricted to planer graphs with maximum degree at most four. We then show that for every graph G without isolated vertices, oitR(G) < ctdR(G) < 2 oitR(G) and for every tree T, 2-(T) + 1 - ctdR(T) - 4-(T), where oitR(G) and -(T) are the outer independent total Roman domination number of G, and the minimum vertex cover number of T respectively. Moreover we investigate the ctdR of corona of two graphs. [ABSTRACT FROM AUTHOR]

Let G = (V;E) be a given graph of order n. A function f: V ! f0; 1; 2g is an independent Roman dominating function (IRDF) on G if for every vertex v 2 V with f(v) = 0 there is a vertex u adjacent to v with f(u) = 2 and fv 2 V: f(v) > 0g is an independent set. The weight of an IRDF f on G is the value f(V) = P v2V f(v). The minimum weight of an IRDF among all IRDFs on G is called the independent Roman domination number of G. In this paper, we give algorithms for computing the independent Roman domination number of G in O(jV j) time when G = (V;E) is a tree, unicyclic graph or proper interval graph. [ABSTRACT FROM AUTHOR]

For two graphs $F$ and $H$, the relative Turán number ${ex}(H,F)$ is the maximum number of edges in an $F$-free subgraph of $H$. Foucaud, Krivelevich, and Perarnau [SIAM J. Discrete Math., 29 (2015), pp. 65--78] and Perarnau and Reed [Combin. Probab. Comput., 26 (2017), pp. 448--467] studied these quantities as a function of the maximum degree of $H$. In this paper, we study a generalization for uniform hypergraphs. If $F$ is a complete $r$-partite $r$-uniform hypergraph with parts of sizes $s_1,s_2,\dots,s_r$ with each $s_{i + 1}$ sufficiently large relative to $s_i$, then with $1/\beta = \sum_{i = 2}^r \prod_{j = 1}^{i - 1} s_j$ we prove that for any $r$-uniform hypergraph $H$ with maximum degree $\Delta$, ${ex}(H,F)\ge \Delta^{-\beta - o(1)} \cdot e(H).$ This is tight as $\Delta \rightarrow \infty$ up to the $o(1)$ term in the exponent, since we show there exists a $\Delta$-regular $r$-graph $H$ such that ${ex}(H,F)=O(\Delta^{-\beta}) \cdot e(H)$. Similar tight results are obtained when $H$ is the random $n$-vertex $r$-graph $H_{n,p}^r$ with edge-probability $p$, extending results of Balogh and Samotij [J. Lond. Math. Soc., 83 (2011), pp. 1091--1094] and Morris and Saxton [Adv. Math., 298 (2016), pp. 534--580]. General lower bounds for a wider class of $F$ are also obtained. [ABSTRACT FROM AUTHOR]