In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number ${\gamma }_{\times 2}\left(G\right)$. A function f(p) is defined, and it is shown that ${\gamma }_{\times 2}\left(G\right)=minf\left(p\right)$, where the minimum is taken over the n-dimensional cube $Cⁿ=p=(p₁,...,pₙ)|p_i\in IR,0\le p_i\le 1,i=1,...,n$. Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then ${\gamma }_{\times 2}\left(G\right)\le ((ln(1+d)+ln\delta +1)/\delta )n$.

A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number ${\gamma }_L\left(G\right)$ is the minimum cardinality of a LDS of G, and the upper locating-domination number, ${\Gamma }_L\left(G\right)$ is the maximum cardinality of a minimal LDS of G. We present different bounds on ${\Gamma }_L\left(G\right)$ and ${\gamma }_L\left(G\right)$.

For a graph $G=(V,E)$, a double Roman dominating function is a function $f:V\to \{0,1,2,3\}$ having the property that if $f\left(v\right)=0$, then the vertex $v$ must have at least two neighbors assigned $2$ under $f$ or one neighbor with $f\left(w\right)=3$, and if $f\left(v\right)=1$, then the vertex $v$ must have at least one neighbor with $f\left(w\right)\ge 2$. The weight of a double Roman dominating function $f$ is the sum $f\left(V\right)={\sum }_{v\in V}f\left(v\right)$. The minimum weight of a double Roman dominating function on $G$ is called the double Roman domination number of $G$ and is denoted by ${\gamma }_{\mathrm{dR}}\left(G\right)$. In this paper, we establish a new...

Let $G$ be a finite group and construct a graph $\Delta \left(G\right)$ by taking $G\setminus \left\{1\right\}$ as the vertex set of $\Delta \left(G\right)$ and by drawing an edge between two vertices $x$ and $y$ if $\langle x,y\rangle$ is cyclic. Let $K\left(G\right)$ be the set consisting of the universal vertices of $\Delta \left(G\right)$ along the identity element. For a solvable group $G$, we present a necessary and sufficient condition for $K\left(G\right)$ to be nontrivial. We also develop a connection between $\Delta \left(G\right)$ and $K\left(G\right)$ when $\left|G\right|$ is divisible by two distinct primes and the diameter of $\Delta \left(G\right)$ is 2.

The line graph of a graph $G$, denoted by $L\left(G\right)$, has $E\left(G\right)$ as its vertex set, where two vertices in $L\left(G\right)$ are adjacent if and only if the corresponding edges in $G$ have a vertex in common. For a graph $H$, define ${\overline{\sigma }}_2\left(H\right)=min\{d\left(u\right)+d\left(v\right):uv\in E\left(H\right)\}$. Let $H$ be a 2-connected claw-free simple graph of order $n$ with $\delta \left(H\right)\ge 3$. We show that, if ${\overline{\sigma }}_2\left(H\right)\ge \frac{1}{7}(2n-5)$ and $n$ is sufficiently large, then either $H$ is traceable or the Ryjáček’s closure $\mathrm{cl}\left(H\right)=L\left(G\right)$, where $G$ is an essentially $2$-edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10...

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g(n,l)$, the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$. By edit distance of two graphs $G$, $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$. This new extremal number $g(n,l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show...

For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number ${\beta }_D\left(G\right)$ is the maximum cardinality of a D-independent set. In particular, the independence number $\beta \left(G\right)={\beta }_1\left(G\right)$. Along with general results we consider, in particular, the odd-independence number ${\beta }_{ODD}\left(G\right)$ where ODD = 1,3,5,....

A graph $G=(V,E)$ is called improperly $(d_1,\cdots ,d_k)$-colorable if the vertex set $V$ can be partitioned into subsets $V_1,\cdots ,V_k$ such that the graph $G\left[V_i\right]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1\le i\le k$. In this paper, we mainly study the improper coloring of $1$-planar graphs and show that $1$-planar graphs with girth at least $7$ are $(2,0,0,0)$-colorable.

For a fixed positive integer $k$ and $G=(V,E)$ a connected graph of order $n$, whose minimum vertex degree is at least $k$, a set $S\subseteq V$ is a total $k$-dominating set, also known as a $k$-tuple total dominating set, if every vertex $v\in V$ has at least $k$ neighbors in $S$. The minimum size of a total $k$-dominating set for $G$ is called the total $k$-domination number of $G$, denoted by ${\gamma }_{kt}\left(G\right)$. The total $k$-domination problem is to determine a minimum total $k$-dominating set of $G$. Since the exact problem is in general quite difficult...

Let $G$ be a simple connected graph with vertex set $V\left(G\right)=\{v_1,v_2,\cdots ,v_n\}$ and edge set $E\left(G\right)$, and let $d_{v_i}$ be the degree of the vertex $v_i$. Let $D\left(G\right)$ be the distance matrix and let $T_r\left(G\right)$ be the diagonal matrix of the vertex transmissions of $G$. The generalized distance matrix of $G$ is defined as $D_{\alpha }\left(G\right)=\alpha T_r\left(G\right)+(1-\alpha )D\left(G\right)$, where $0\le \alpha \le 1$. Let ${\lambda }_1\left(D_{\alpha }\left(G\right)\right)\ge {\lambda }_2\left(D_{\alpha }\left(G\right)\right)\ge ...\ge {\lambda }_n\left(D_{\alpha }\left(G\right)\right)$ be the generalized distance eigenvalues of $G$, and let $k$ be an integer with $1\le k\le n$. We denote by $S_k\left(D_{\alpha }\left(G\right)\right)={\lambda }_1\left(D_{\alpha }\left(G\right)\right)+{\lambda }_2\left(D_{\alpha }\left(G\right)\right)+...+{\lambda }_k\left(D_{\alpha }\left(G\right)\right)$ the sum of the $k$ largest generalized distance eigenvalues. The generalized distance spread of a graph $G$ is defined as $D_{\alpha }S\left(G\right)={\lambda }_1\left(D_{\alpha }\left(G\right)\right)-{\lambda }_n\left(D_{\alpha }\left(G\right)\right)$....

Let $ex(n,G)$ denote the maximum number of edges in a graph on $n$ vertices which does not contain $G$ as a subgraph. Let $P_i$ denote a path consisting of $i$ vertices and let $m{P}_i$ denote $m$ disjoint copies of $P_i$. In this paper we count $ex(n,3P_4)$.

Let $T$ be a tree. Then a vertex of $T$ with degree one is a leaf of $T$ and a vertex of degree at least three is a branch vertex of $T$. The set of leaves of $T$ is denoted by $L\left(T\right)$ and the set of branch vertices of $T$ is denoted by $B\left(T\right)$. For two distinct vertices $u$, $v$ of $T$, let $P_T[u,v]$ denote the unique path in $T$ connecting $u$ and $v.$ Let $T$ be a tree with $B\left(T\right)\ne \varnothing$. For each leaf $x$ of $T$, let $y_x$ denote the nearest branch vertex to $x$. We delete $V\left(P_T[x,y_x]\right)\setminus \left\{y_x\right\}$ from $T$ for all $x\in L\left(T\right)$. The resulting subtree of $T$ is called the reducible stem...

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let $G$ be a bridgeless simple graph with minimum degree at least $3$. Jackson and Yoshimoto (2007) showed that $G$ has an even factor containing two arbitrary prescribed edges. They also proved that $G$ has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges $e_1$ and $e_2$ of $G$, there is an even factor containing $e_1$ and $e_2$...

Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$ contains a $G_2$. Parsons gave a recursive formula to determine the values of $R(P_n,K_{1,m})$, where $P_n$ is a path on $n$ vertices and $K_{1,m}$ is a star on $m+1$ vertices. In this note, we study the Ramsey numbers $R(P_n,K_1\vee F_m)$, where $F_m$ is a linear forest on $m$ vertices. We determine the exact values of $R(P_n,K_1\vee F_m)$ for the cases $m\le n$ and $m\ge 2n$, and for the case that $F_m$ has no odd component. Moreover, we...