A Roman dominating function (RDF) on a graph G = (V,E) is a function f : V −→ {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF is the value f(V (G)) = P u2V (G) f(u). An RDF f in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number R(G) (respectively, the independent Roman domination number iR(G)) is the minimum weight of an RDF (respectively,...

Let G be a graph and f : V (G) → {2, 3, . . .}. A spanning subgraph F is called strong f-star of G if each component of F is a star whose center x satisfies degF (x) ≤ ƒ(x) and F is an induced subgraph of G. In this paper, we prove that G has a strong f-star factor if and only if oddca(G − S) ≤ ∑x∊S ƒ(x) for all S ⊂ V (G), where oddca(G) denotes the number of odd complete-cacti of G.

For positive integers d and m, let $P_{d,m}\left(G\right)$ denote the property that between each pair of vertices of the graph G, there are m internally vertex disjoint paths of length at most d. For a positive integer t a graph G satisfies the minimum generalized degree condition δₜ(G) ≥ s if the cardinality of the union of the neighborhoods of each set of t vertices of G is at least s. Generalized degree conditions that ensure that $P_{d,m}\left(G\right)$ is satisfied have been investigated. In particular, it has been shown, for fixed positive...

A graph with p vertices is said to be strongly multiplicative if its vertices can be labelled 1,2,...,p so that the values on the edges, obtained as the product of the labels of their end vertices, are all distinct. In this paper, we study structural properties of strongly multiplicative graphs. We show that all graphs in some classes, including all trees, are strongly multiplicative, and consider the question of the maximum number of edges in a strongly multiplicative graph of a given order.

Say that a cycle C almost contains a cycle C¯ if every edge except one of C¯ is an edge of C. Call a graph G strongly pancyclic if every nontriangular cycle C almost contains another cycle C¯ and every nonspanning cycle C is almost contained in another cycle C⁺. This is equivalent to requiring, in addition, that the sizes of C¯ and C⁺ differ by one from the size of C. Strongly pancyclic graphs are pancyclic and chordal, and their cycles enjoy certain interpolation and extrapolation properties with...

This article, one of a series, approaches the topics of marriage and kinship through a revitalized kinetic structural approach that shifts the primary focus from abstract models of rules, terminologies, attitudes and norms to exploration of concrete relations in a population, analyzed graph-theoretically in their full complexity as networks. Network representation using the graphe de parenté (see below) serves as the basis for examining marriage alliance theory, population structure (such as endogamy...

A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n1, . . . , np) of |V (G)| there exists a partition (V1, . . . , Vp) of V (G) such that each Vi induces a connected subgraph of G on ni vertices. Some stronger versions of this property were introduced, namely the ones of being online arbitrarily partitionable and recursively arbitrarily partitionable (OL-AP and R-AP for short, respectively), in which the subgraphs induced by a partition of G must...

A graph is k-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most k. These graphs were introduced by Lick and White in 1970 and have been studied in several subsequent papers. We present sharp bounds on the diameter of maximal k-degenerate graphs and characterize the extremal graphs for the upper bound. We present a simple characterization of the degree sequences of these graphs and consider related results. Considering edge coloring, we conjecture...

Let ${\mathbb{Z}}_n\left[\mathrm{i}\right]$ be the ring of Gaussian integers modulo $n$. We construct for ${\mathbb{Z}}_n\left[\mathrm{i}\right]$ a cubic mapping graph $\Gamma \left(n\right)$ whose vertex set is all the elements of ${\mathbb{Z}}_n\left[\mathrm{i}\right]$ and for which there is a directed edge from $a\in {\mathbb{Z}}_n\left[\mathrm{i}\right]$ to $b\in {\mathbb{Z}}_n\left[\mathrm{i}\right]$ if $b=a^3$. This article investigates in detail the structure of $\Gamma \left(n\right)$. We give suffcient and necessary conditions for the existence of cycles with length $t$. The number of $t$-cycles in ${\Gamma }_1\left(n\right)$ is obtained and we also examine when a vertex lies on a $t$-cycle of ${\Gamma }_2\left(n\right)$, where ${\Gamma }_1\left(n\right)$ is induced by all the units of ${\mathbb{Z}}_n\left[\mathrm{i}\right]$ while ${\Gamma }_2\left(n\right)$ is induced by all the...

Let (W,S) be a Coxeter system such that no two generators in S commute. Assume that the Cayley graph of (W,S) does not contain adjacent hexagons. Then for any two vertices x and y in the Cayley graph of W and any number k ≤ d = dist(x,y) there are at most two vertices z such that dist(x,z) = k and dist(z,y) = d - k. Allowing adjacent hexagons, but assuming that no three hexagons can be adjacent to each other, we show that the number of such intermediate vertices at a given distance from x and y...