Abstract For a maximal outerplanar graph G of order n at least three, Matheson and Tarjan showed that has domination number most . Similarly, for five, Dorfling, Hattingh, Jonck showed, by completely different approach, total unless is isomorphic to one two exceptional graphs 12. We present unified proof common generalization these results. every positive integer k , we specify set such does not belong dominating D component the subgraph induced

The domination number γ(G), the independent ι(G), connected γ c (G), and paired p (G) of a graph G (without isolated vertices, if necessary) are related by simple inequalities γ(G) ≤ (G). Very little is known about graphs that satisfy one these with equality.I.E.Zverovich V.E.Zverovich studied classes defined requiring equality in first two above for all induced subgraphs necessary).In this article we prove hardness results which suggest extremal some do not have structure.

The celebrated canonical Ramsey theorem of Erd\H{o}s and Rado implies that for $2\leq k\in \mathbb{N}$, any colouring the edges $K_n$ with $n$ sufficiently large gives a copy $C_{2k}$ which has one three colour patterns: monochromatic, rainbow or lexicographic. In this paper we show if $p=\omega(n^{-1+1/(2k-1)}\log n)$, then ${\mathbf{G}}(n,p)$ will asymptotically almost surely also have property its induces copies $C_{2k}$. This determines threshold respect to even cycles, up $\log$ factor.

For a graph G, let γ R (G) and r2 denote the Roman domination number of G 2-rainbow respectively.It is known that ≤ 3 2 (G).Fujita Furuya [Difference between in graphs, Discrete Appl.Math.161 (2013) 806-812] present some kind characterization graphs for which -γ = k integer k.Unfortunately, their result does not lead to an algorithm allows recognize these efficiently.We show every fixed non-negative k, recognition connected K 4 -free with NP-hard, implies there most likely no good graphs.We...

Addressing a problem posed by Chellali, Haynes, and Hedetniemi (Discrete Appl. Math. 178 (2014) 27-32) we prove $\gamma_{r2}(G)\leq 2\gamma_r(G)$ for every graph $G$, where $\gamma_{r2}(G)$ $\gamma_r(G)$ denote the $2$-rainbow domination number weak Roman of respectively. We characterize extremal graphs this inequality that are $\{ K_4,K_4-e\}$-free, show recognition $K_5$-free is NP-hard.

Given a graph G and vertex v ∈ G, the chromatic neighbourhood of is set colours its incident edges. An adjacent-vertex-distinguishing total colouring (AVDTC) proper which every two adjacent vertices on have different neighbourhood. It was conjectured in 2005 that minimum number guarantees existence an AVDTC with these colours, χa″(G), bounded from above by Δ(G) + 3 for any G. In this work we prove validity conjecture hypercubes, lattice graphs powers cycles Ckn when either (i) k = 2 n ≥ 6,...

For a graph $G$, let $\gamma_R(G)$ and $\gamma_{r2}(G)$ denote the Roman domination number of $G$ $2$-rainbow respectively. It is known that $\gamma_{r2}(G)\leq \gamma_R(G)\leq \frac{3}{2}\gamma_{r2}(G)$. Fujita Furuya (Difference between 2-rainbow in graphs, Discrete Applied Mathematics 161 (2013) 806-812) present some kind characterization graphs for which $\gamma_R(G)-\gamma_{r2}(G)=k$ integer $k$. Unfortunately, their result does not lead to an algorithm allows recognize these...

For a graph $G$, let $\gamma_{r2}(G)$ and $\gamma_R(G)$ denote the $2$-rainbow domination number Roman number, respectively. Fujita Furuya (Difference between 2-rainbow in graphs, Discrete Applied Mathematics 161 (2013) 806-812) proved $\gamma_{r2}(G)+\gamma_R(G)\leq \frac{6}{4}n(G)$ for connected $G$ of order $n(G)$ at least $3$. Furthermore, they conjectured \frac{4}{3}n(G)$ minimum degree $2$ that is distinct from $C_5$. We characterize all extremal graphs their inequality prove conjecture.

We provide a constructive characterization of the trees for which Roman domination number strongly equals weak number, that is, every dominating function minimum weight is function. Our based on five simple extension operations, and reveals several structural properties these trees.

For a maximal outerplanar graph $G$ of order $n$ at least $3$, Matheson and Tarjan showed that has domination number most $n/3$. Similarly, for $5$, Dorfling, Hattingh, Jonck showed, by completely different approach, total $2n/5$ unless is isomorphic to one two exceptional graphs $12$. We present unified proof common generalization these results. every positive integer $k$, we specify set ${\cal H}_k$ $4k+4$ $4k^2-2k$ such $2k+1$ does not belong dominating $D$ $\lfloor\frac{kn}{2k+1}\rfloor$...

The celebrated canonical Ramsey theorem of Erd\H{o}s and Rado implies that for a given graph $H$, if $n$ is sufficiently large then any colouring the edges $K_n$ gives rise to copies $H$ exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. We are interested in sparse random versions this result threshold at which $G(n,p)$ inherits properties $K_n$. Our main here pins down when we focus on colourings constrained by some prefixed lists. This applied an accompanying...

Two recent papers~\cite{GGS} and~\cite{NRS22} study the lower tail of triangle count deviations in random graphs $G(n,m)$ with positive density $t:=m/\binom{n}{2}\in (0,1)$. Let us write $D_{\triangle}(G)$ for deviation from its mean. Results of~\cite{GGS} determine order magnitude log probability $\log(\pr{D_{\triangle}(G(n,m)) \, < - \tau\binom{n}{3}})$ ranges $n^{-3/2}\ll \tau\ll n^{-1}$ and $n^{-3/4}\ll\tau\ll 1$ respectively. Furthermore, in~\cite{NRS22} it is proved that at least...

The celebrated canonical Ramsey theorem of Erdős and Rado implies that for a given graph H, if n is sufficiently large then any colouring the edges Kn gives rise to copies H exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. We are interested in sparse random versions this result threshold at which G(n,p) inherits properties Kn. Our main here pins down when we focus on colourings constrained by some prefixed lists. This applied an accompanying work authors...

We study the emergence of loose Hamilton cycles in subgraphs random hypergraphs. Our main result states that minimum $d$-degree threshold for Hamiltonicity relative to $k$-uniform hypergraph $H_k(n,p)$ coincides with its dense analogue whenever $p \geq n^{- (k-1)/2+o(1)}$. The value $p$ is approximately tight $d>(k+1)/2$. This particularly interesting because itself not known beyond cases when $d k-2$.