The fundamental constituents of iteration digraphs of finite commutative rings

Jizhu Nan; Yangjiang Wei; Gaohua Tang

Displaying similar documents to “The fundamental constituents of iteration digraphs of finite commutative rings”

On a problem of E. Prisner concerning the biclique operator

Bohdan Zelinka (2002)

Mathematica Bohemica

Similarity:

The symbol $K (B, C)$ denotes a directed graph with the vertex set $B \cup C$ for two (not necessarily disjoint) vertex sets $B, C$ in which an arc goes from each vertex of $B$ into each vertex of $C$ . A subdigraph of a digraph $D$ which has this form is called a bisimplex in $D$ . A biclique in $D$ is a bisimplex in $D$ which is not a proper subgraph of any other and in which $B \neq \emptyset$ and $C \neq \emptyset$ . The biclique digraph $\vec{C} (D)$ of $D$ is the digraph whose vertex set is the set of all bicliques in $D$ and in which there is an arc from $K (B_{1}, C_{1})$ into $K (B_{2}, C_{2})$ ...

On-line ranking number for cycles and paths

Erik Bruoth, Mirko Horňák (1999)

Discussiones Mathematicae Graph Theory

Similarity:

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 $χ *_{r} (G)$ 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 $χ *_{r} (P ₙ) < 3 l o g ₂ n$ for n ≥ 2....

A note on arc-disjoint cycles in tournaments

Jan Florek (2014)

Colloquium Mathematicae

Similarity:

We prove that every vertex v of a tournament T belongs to at least $m a x m i n δ ⁺ (T), 2 δ ⁺ (T) - d ⁺_{T} (v) + 1, m i n δ ¯ (T), 2 δ ¯ (T) - d ¯_{T} (v) + 1$ arc-disjoint cycles, where δ⁺(T) (or δ¯(T)) is the minimum out-degree (resp. minimum in-degree) of T, and $d ⁺_{T} (v)$ (or $d ¯_{T} (v)$ ) is the out-degree (resp. in-degree) of v.

Sum labellings of cycle hypergraphs

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph is a sum hypergraph iff there are a finite S ⊆ IN⁺ and d̲, [d̅] ∈ IN⁺ with 1 < d̲ ≤ [d̅] such that is isomorphic to the hypergraph $_{d ̲, [d ̅]} (S) = (V,)$ where V = S and $= e \subseteq S : d ̲ \leq | e | \leq [d ̅] \land \sum_{v \in e} v \in S$ . For an arbitrary hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $y ₁, . . ., y_{σ} \notin V$ such that $\cup y ₁, . . ., y_{σ}$ is a sum hypergraph. Generalizing the graph Cₙ we obtain d-uniform hypergraphs where any d consecutive vertices of Cₙ form an edge. We determine sum numbers and investigate properties of sum labellings...

On the heterochromatic number of circulant digraphs

Hortensia Galeana-Sánchez, Víctor Neumann-Lara (2004)

Discussiones Mathematicae Graph Theory

Similarity:

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 (D_{n, s})$ is the set of integers mod 2n+1 and $A (D_{n, s}) = (i, j) : j - i \in 1, 2, . . ., n ∖ s . .$ In this paper we prove that $h c (D_{n, s}) \leq 5$ for n ≥ 7. The bound is tight since equality holds when s ∈ n,[(2n+1)/3].

The classification of finite groups by using iteration digraphs

Uzma Ahmad, Muqadas Moeen (2016)

Czechoslovak Mathematical Journal

Similarity:

A digraph is associated with a finite group by utilizing the power map $f : G \to G$ defined by $f (x) = x^{k}$ for all $x \in G$ , where $k$ is a fixed natural number. It is denoted by $γ_{G} (n, k)$ . In this paper, the generalized quaternion and $2$ -groups are studied. The height structure is discussed for the generalized quaternion. The necessary and sufficient conditions on a power digraph of a $2$ -group are determined for a $2$ -group to be a generalized quaternion group. Further, the classification of two generated $2$ -groups as abelian...

On locating and differentiating-total domination in trees

Mustapha Chellali (2008)

Discussiones Mathematicae Graph Theory

Similarity:

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 $γ ₜ^{L} (G)$ and $γ ₜ^{D} (G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total...

Signed domination and signed domatic numbers of digraphs

Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a finite and simple digraph with the vertex set V(D), and let f:V(D) → -1,1 be a two-valued function. If $\sum_{x \in N ¯ [v]} f (x) \geq 1$ for each v ∈ V(D), where N¯[v] consists of v and all vertices of D from which arcs go into v, then f is a signed dominating function on D. The sum f(V(D)) is called the weight w(f) of f. The minimum of weights w(f), taken over all signed dominating functions f on D, is the signed domination number $γ_{S} (D)$ of D. A set $f ₁, f ₂, . . ., f_{d}$ of signed dominating functions on D with the property that...

Pairs of forbidden class of subgraphs concerning $K_{1, 3}$ and P₆ to have a cycle containing specified vertices

Takeshi Sugiyama, Masao Tsugaki (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1, 3}$ and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair $K_{1, 3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.

On the tree structure of the power digraphs modulo $n$

Amplify Sawkmie, Madan Mohan Singh (2015)

Czechoslovak Mathematical Journal

Similarity:

For any two positive integers $n$ and $k \geq 2$ , let $G (n, k)$ be a digraph whose set of vertices is ${0, 1, ..., n - 1}$ and such that there is a directed edge from a vertex $a$ to a vertex $b$ if $a^{k} \equiv b (mod n)$ . Let $n = \prod_{i = 1}^{r} p_{i}^{e_{i}}$ be the prime factorization of $n$ . Let $P$ be the set of all primes dividing $n$ and let $P_{1}, P_{2} \subseteq P$ be such that $P_{1} \cup P_{2} = P$ and $P_{1} \cap P_{2} = \emptyset$ . A fundamental constituent of $G (n, k)$ , denoted by $G_{P_{2}}^{*} (n, k)$ , is a subdigraph of $G (n, k)$ induced on the set of vertices which are multiples of $\prod_{p_{i} \in P_{2}} p_{i}$ and are relatively prime to all primes $q \in P_{1}$ . L. Somer and M. Křížek proved that the trees attached...

Some results on the annihilator graph of a commutative ring

Mojgan Afkhami, Kazem Khashyarmanesh, Zohreh Rajabi (2017)

Czechoslovak Mathematical Journal

Similarity:

Let $R$ be a commutative ring. The annihilator graph of $R$ , denoted by $AG (R)$ , is the undirected graph with all nonzero zero-divisors of $R$ as vertex set, and two distinct vertices $x$ and $y$ are adjacent if and only if ${ann}_{R} (x y) \neq {ann}_{R} (x) \cup {ann}_{R} (y)$ , where for $z \in R$ , ${ann}_{R} (z) = {r \in R : r z = 0}$ . In this paper, we characterize all finite commutative rings $R$ with planar or outerplanar or ring-graph annihilator graphs. We characterize all finite commutative rings $R$ whose annihilator graphs have clique number $1$ , $2$ or $3$ . Also, we investigate some properties...

Fires on trees

Jean Bertoin (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

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^{- α}$ 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...