For each vertex v in a graph G, let there be associated a subgraph $H_v$ of G. The vertex v is said to dominate $H_v$ as well as dominate each vertex and edge of $H_v$. A set S of vertices of G is called a full dominating set if every vertex of G is dominated by some vertex of S, as is every edge of G. The minimum cardinality of a full dominating set of G is its full domination number ${\gamma }_{FH}\left(G\right)$. A full dominating set of G of cardinality ${\gamma }_{FH}\left(G\right)$ is called a ${\gamma }_{FH}$-set of G. We study three types of full domination in...

A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number $\chi {*}_r\left(G\right)$ of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that $\chi {*}_r\left(Pₙ\right)<3log₂n$ for n ≥ 2....

The heterochromatic number hc(D) of a digraph D, is the minimum integer k such that for every partition of V(D) into k classes, there is a cyclic triangle whose three vertices belong to different classes. For any two integers s and n with 1 ≤ s ≤ n, let $D_{n,s}$ be the oriented graph such that $V\left(D_{n,s}\right)$ is the set of integers mod 2n+1 and $A\left(D_{n,s}\right)=(i,j):j-i\in 1,2,...,n\setminus s..$In this paper we prove that $hc\left(D_{n,s}\right)\le 5$ for n ≥ 7. The bound is tight since equality holds when s ∈ n,[(2n+1)/3].

A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $\gamma {ₜ}^L\left(G\right)$ and $\gamma {ₜ}^D\left(G\right)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total...

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $s{d}_{\gamma }\left(G\right)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1\le s{d}_{\gamma }\left(G\right)\le 3$ for any graph G. We give a counterexample to this conjecture. On the other hand,...

A method for the second-order approximation of the values of partial derivatives of an arbitrary smooth function $u=u(x_1,x_2)$ in the vertices of a conformal and nonobtuse regular triangulation ${𝒯}_h$ consisting of triangles and convex quadrilaterals is described and its accuracy is illustrated numerically. The method assumes that the interpolant ${\Pi }_h\left(u\right)$ in the finite element space of the linear triangular and bilinear quadrilateral finite elements from ${𝒯}_h$ is known only.

For an ordered set $W=\{w_1,w_2,...,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the ordered $k$-vector $r\left(v\right|W):=(d(v,w_1),d(v,w_2),...,d(v,w_k))$ is called the metric representation of $v$ with respect to $W$, where $d(x,y)$ is the distance between vertices $x$ and $y$. A set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. The minimum cardinality of a resolving set for $G$ is its metric dimension. In this paper, we characterize all graphs of order $n$ with metric dimension $n-3$.

We effectively construct in the Hilbert cube $ℍ={[0,1]}^{\omega }$ two sets $V,W\subset ℍ$ with the following properties: (a) $V\cap W=\varnothing$, (b) $V\cup W$ is discrete-dense, i.e. dense in ${{[0,1]}_D}^{\omega }$, where ${[0,1]}_D$ denotes the unit interval equipped with the discrete topology, (c) $V$, $W$ are open in $ℍ$. In fact, $V={\bigcup }_{\mathbb{N}}{V}_i$, $W={\bigcup }_{\mathbb{N}}{W}_i$, where $V_i={\bigcup }_0^{2^{i-1}-1}{V}_{ij}$, $W_i={\bigcup }_0^{2^{i-1}-1}{W}_{ij}$. $V_{ij}$, $W_{ij}$ are basic open sets and $(0,0,0,...)\in V_{ij}$, $(1,1,1,...)\in W_{ij}$, (d) $V_i\cup W_i$, $i\in \mathbb{N}$ is point symmetric about $(1/2,1/2,1/2,...)$. Instead of $[0,1]$ we could have taken any $T_4$-space or a digital interval, where the resolution (number of points) increases with $i$.

We consider random dynamics on the edges of a uniform Cayley tree with $n$ vertices, in which edges are either flammable, fireproof, or burnt. Every flammable edge is replaced by a fireproof edge at unit rate, while fires start at smaller rate $n^{-\alpha }$ on each flammable edge, then propagate through the neighboring flammable edges and are only stopped at fireproof edges. A vertex is called fireproof when all its adjacent edges are fireproof. We show that as $n\to \infty$, the terminal density of fireproof...

In this paper we show bounds for the adjacent eccentric distance sum of graphs in terms of Wiener index, maximum degree and minimum degree. We extend some earlier results of Hua and Yu [Bounds for the Adjacent Eccentric Distance Sum, International Mathematical Forum, Vol. 7 (2002) no. 26, 1289–1294]. The adjacent eccentric distance sum index of the graph $G$ is defined as$${\xi }^{sv}\left(G\right)=\sum _{v\in V\left(G\right)}\frac{\epsilon \left(v\right)D\left(v\right)}{deg\left(v\right)},$$ where $\epsilon \left(v\right)$ is the eccentricity of the vertex $v$, $deg\left(v\right)$ is the degree of the vertex $v$ and$$D\left(v\right)=\sum _{u\in V\left(G\right)}d(u,v)$$ is the sum of all distances from...

This paper is about $0/1$-triangles, which are the simplest nontrivial examples of $0/1$-polytopes: convex hulls of a subset of vertices of the unit $n$-cube $I^n$. We consider the subclasses of right $0/1$-triangles, and acute $0/1$-triangles, which only have acute angles. They can be explicitly counted and enumerated, also modulo the symmetries of $I^n$.

For vertices x and y in a connected graph G, the detour distance D(x,y) is the length of a longest x - y path in G. An x - y path of length D(x,y) is an x - y detour. The closed detour interval ID[x,y] consists of x,y, and all vertices lying on some x -y detour of G; while for S ⊆ V(G), $I_D\left[S\right]={\bigcup }_{x,y\in S}{I}_D[x,y]$. A set S of vertices is a detour convex set if $I_D\left[S\right]=S$. The detour convex hull ${\left[S\right]}_D$ is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of...

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 ring $R$ is called a right $\mathrm{PS}$-ring if its socle, $\mathrm{Soc}\left(R_R\right)$, is projective. Nicholson and Watters have shown that if $R$ is a right $\mathrm{PS}$-ring, then so are the polynomial ring $R\left[x\right]$ and power series ring $R\left[\right[x\left]\right]$. In this paper, it is proved that, under suitable conditions, if $R$ has a (flat) projective socle, then so does the skew inverse power series ring $R\left[[x^{-1};\alpha ,\delta ]\right]$ and the skew polynomial ring $R[x;\alpha ,\delta ]$, where $R$ is an associative ring equipped with an automorphism $\alpha$ and an $\alpha$-derivation $\delta$. Our results extend and unify many existing...