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.