Let k ≥ 1 be an integer, and G = (V, E) be a finite and simple graph. The closed neighborhood NG[e] of an edge e in a graph G is the set consisting of e and all edges having a common end-vertex with e. A signed Roman edge k-dominating function (SREkDF) on a graph G is a function f : E → {−1, 1, 2} satisfying the conditions that (i) for every edge e of G, ∑x∈NG[e] f(x) ≥ k and (ii) every edge e for which f(e) = −1 is adjacent to at least one edge e′ for which f(e′) = 2. The minimum of the values...

The signed total domination number of a graph is a certain variant of the domination number. If $v$ is a vertex of a graph $G$, then $N\left(v\right)$ is its oper neighbourhood, i.e. the set of all vertices adjacent to $v$ in $G$. A mapping $f:V\left(G\right)\to \{-1,1\}$, where $V\left(G\right)$ is the vertex set of $G$, is called a signed total dominating function (STDF) on $G$, if ${\sum }_{x\in N\left(v\right)}f\left(x\right)\ge 1$ for each $v\in V\left(G\right)$. The minimum of values ${\sum }_{x\in V\left(G\right)}f\left(x\right)$, taken over all STDF’s of $G$, is called the signed total domination number of $G$ and denoted by ${\gamma }_{\mathrm{s}t}\left(G\right)$. A theorem stating lower bounds for ${\gamma }_{\mathrm{s}t}\left(G\right)$ is stated for the...

Let D be a finite and simple digraph with vertex set V (D). A signed total Roman dominating function (STRDF) on a digraph D is a function f : V (D) → {−1, 1, 2} satisfying the conditions that (i) ∑x∈N−(v) f(x) ≥ 1 for each v ∈ V (D), where N−(v) consists of all vertices of D from which arcs go into v, and (ii) every vertex u for which f(u) = −1 has an inner neighbor v for which f(v) = 2. The weight of an STRDF f is w(f) = ∑v∈V (D) f(v). The signed total Roman domination number γstR(D) of D is the...

By a ternary system we mean an ordered pair $(W,R)$, where $W$ is a finite nonempty set and $R\subseteq W\times W\times W$. By a signpost system we mean a ternary system $(W,R)$ satisfying the following conditions for all $x,y,z\in W$: if $(x,y,z)\in R$, then $(y,x,x)\in R$ and $(y,x,z)\notin R$; if $x\ne y$, then there exists $t\in W$ such that $(x,t,y)\in R$. In this paper, a signpost system is used as a common description of a connected graph and a spanning tree of the graph. By a ct-pair we mean an ordered pair $(G,T)$, where $G$ is a connected graph and $T$ is a spanning tree of $G$. If $(G,T)$ is a ct-pair, then by the guide to...

Harary [10, p. 7] claims that Veblen [20, p. 2] first suggested to formalize simple graphs using simplicial complexes. We have developed basic terminology for simple graphs as at most 1-dimensional complexes. We formalize this new setting and then reprove Mycielski’s [12] construction resulting in a triangle-free graph with arbitrarily large chromatic number. A different formalization of similar material is in [15].

Define a complete subgraph Q to be simplicial in a graph G when Q is contained in exactly one maximal complete subgraph ('maxclique') of G; otherwise, Q is nonsimplicial. Several graph classes-including strong p-Helly graphs and strongly chordal graphs-are shown to have pairs of peculiarly related new characterizations: (i) for every k ≤ 2, a certain property holds for the complete subgraphs that are in k or more maxcliques of G, and (ii) in every induced subgraph H of G, that same property...