Signed total distance -domatic numbers of graphs
The signed total domination number of a graph is a certain variant of the domination number. If is a vertex of a graph , then is its oper neighbourhood, i.e. the set of all vertices adjacent to in . A mapping , where is the vertex set of , is called a signed total dominating function (STDF) on , if for each . The minimum of values , taken over all STDF’s of , is called the signed total domination number of and denoted by . A theorem stating lower bounds for 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 , where is a finite nonempty set and . By a signpost system we mean a ternary system satisfying the following conditions for all : if , then and ; if , then there exists such that . 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 , where is a connected graph and is a spanning tree of . If 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...