Decompositions of nearly complete digraphs into t isomorphic parts

Mariusz Meszka; Zdzisław Skupień

Displaying similar documents to “Decompositions of nearly complete digraphs into t isomorphic parts”

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...

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.

Self-diclique circulant digraphs

Marietjie Frick, Bernardo Llano, Rita Zuazua (2015)

Mathematica Bohemica

Similarity:

We study a particular digraph dynamical system, the so called digraph diclique operator. Dicliques have frequently appeared in the literature the last years in connection with the construction and analysis of different types of networks, for instance biochemical, neural, ecological, sociological and computer networks among others. Let $D = (V, A)$ be a reflexive digraph (or network). Consider $X$ and $Y$ (not necessarily disjoint) nonempty subsets of vertices (or nodes) of $D$ . A disimplex $K (X, Y)$ of $D$ is...

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 short cycles in triangle-free oriented graphs

Yurong Ji, Shufei Wu, Hui Song (2018)

Czechoslovak Mathematical Journal

Similarity:

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $⌈ n / d ⌉$ . In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that $α_{0}$ is the smallest real such that every $n$ -vertex digraph with minimum outdegree at least $α_{0} n$ contains a directed triangle. Let $ϵ < (3 - 2 α_{0}) / (4 - 2 α_{0})$ be a positive real. We show that if $D$ is an oriented graph...

Majority choosability of 1-planar digraph

Weihao Xia, Jihui Wang, Jiansheng Cai (2023)

Czechoslovak Mathematical Journal

Similarity:

A majority coloring of a digraph $D$ with $k$ colors is an assignment $π : V (D) \to {1, 2, \dots, k}$ such that for every $v \in V (D)$ we have $π (w) = π (v)$ for at most half of all out-neighbors $w \in N^{+} (v)$ . A digraph $D$ is majority $k$ -choosable if for any assignment of lists of colors of size $k$ to the vertices, there is a majority coloring of $D$ from these lists. We prove that if $U (D)$ is a 1-planar graph without a 4-cycle, then $D$ is majority 3-choosable. And we also prove that every NIC-planar digraph is majority 3-choosable.

Iterated arc graphs

Danny Rorabaugh, Claude Tardif, David Wehlau, Imed Zaguia (2018)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

The arc graph $δ (G)$ of a digraph $G$ is the digraph with the set of arcs of $G$ as vertex-set, where the arcs of $δ (G)$ join consecutive arcs of $G$ . In 1981, S. Poljak and V. Rödl characterized the chromatic number of $δ (G)$ in terms of the chromatic number of $G$ when $G$ is symmetric (i.e., undirected). In contrast, directed graphs with equal chromatic numbers can have arc graphs with distinct chromatic numbers. Even though the arc graph of a symmetric graph is not symmetric, we show that the chromatic number...

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...