For any two positive integers $n$ and $k\ge 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(modn)$. 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=\varnothing$. 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 to all cycle...

A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge ê∈ E we explore the question whether the graph G-ê, obtained by removing the undirected edge ê, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.

We introduce object systems as a common generalization of graphs, hypergraphs, digraphs and relational structures. Let C be a concrete category, a simple object system over C is an ordered pair S = (V,E), where E = A₁,A₂,...,Aₘ is a finite set of the objects of C, such that the ground-set $V\left(A_i\right)$ of each object $A_i\in E$ is a finite set with at least two elements and $V\supseteq {\bigcup }_{i=1}^{m}V\left(A_i\right)$. To generalize the results on graph colourings to simple object systems we define, analogously as for graphs, that an additive induced-hereditary...

In this paper we investigate varieties of orgraphs (that is, oriented graphs) as classes of orgraphs closed under isomorphic images, suborgraph identifications and induced suborgraphs, and we study the lattice of varieties of tournament-free orgraphs.

Let $D$ be an oriented graph of order $n$ and size $m$. A $\gamma$-labeling of $D$ is a one-to-one function $fV\left(D\right)\to \{0,1,2,...,m\}$ that induces a labeling $f^{\text{'}}E\left(D\right)\to \{\pm 1,\pm 2,...,\pm m\}$ of the arcs of $D$ defined by $f^{\text{'}}\left(e\right)=f\left(v\right)-f\left(u\right)$ for each arc $e=(u,v)$ of $D$. The value of a $\gamma$-labeling $f$ is $\mathrm{v}al\left(f\right)={\sum }_{e\in E\left(G\right)}{f}^{\text{'}}\left(e\right).$ A $\gamma$-labeling of $D$ is balanced if the value of $f$ is 0. An oriented graph $D$ is balanced if $D$ has a balanced labeling. A graph $G$ is orientably balanced if $G$ has a balanced orientation. It is shown that a connected graph $G$ of order $n\ge 2$ is orientably balanced unless $G$ is a tree, $n\equiv 2\left(mod4\right)$, and every vertex of...

We investigate congruences in one-element extensions of algebras in the variety generated by tournaments.

Dans cet article, nous essayons de faire le point sur les résultats concernant les aspects combinatoires et algorithmiques des ordres médians et des ordres de Slater des tournois. La plupart des résultats recensés sont tirés de différentes publications ; plusieurs sont originaux.

The orientation distance graph 𝓓ₒ(G) of a graph G is defined as the graph whose vertex set is the pair-wise non-isomorphic orientations of G, and two orientations are adjacent iff the reversal of one edge in one orientation produces the other. Orientation distance graphs was introduced by Chartrand et al. in 2001. We provide new results about orientation distance graphs and simpler proofs to existing results, especially with regards to the bipartiteness of orientation distance graphs and the representation...

We provide the list of all paths with at most $16$ arcs with the property that if a graph $G$ admits an orientation $\overrightarrow{G}$ such that one of the paths in our list admits no homomorphism to $\overrightarrow{G}$, then $G$ is $3$-colourable.

We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs.