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 $\lceil n/d\rceil$. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that ${\alpha }_0$ is the smallest real such that every $n$-vertex digraph with minimum outdegree at least ${\alpha }_{0}n$ contains a directed triangle. Let $ϵ<(3-2{\alpha }_0)/(4-2{\alpha }_0)$ be a positive real. We show that if $D$ is an oriented graph without...

Guaranteed upper bounds on the length of a shortest cycle through k ≤ 5 prescribed vertices of a polyhedral graph or plane triangulation are proved.

The signed distance-$k$-domination number of a graph is a certain variant of the signed domination number. If $v$ is a vertex of a graph $G$, the open $k$-neighborhood of $v$, denoted by $N_k\left(v\right)$, is the set $N_k\left(v\right)=\{u\mid u\ne v$ and $d(u,v)\le k\}$. $N_k\left[v\right]=N_k\left(v\right)\cup \left\{v\right\}$ is the closed $k$-neighborhood of $v$. A function $fV\to \{-1,1\}$ is a signed distance-$k$-dominating function of $G$, if for every vertex $v\in V$, $f\left(N_k\left[v\right]\right)={\sum }_{u\in N_k\left[v\right]}f\left(u\right)\ge 1$. The signed distance-$k$-domination number, denoted by ${\gamma }_{k,s}\left(G\right)$, is the minimum weight of a signed distance-$k$-dominating function on $G$. The values of ${\gamma }_{2,s}\left(G\right)$ are found for graphs with small diameter,...

The signed edge domination number of a graph is an edge variant of the signed domination number. The closed neighbourhood $N_G\left[e\right]$ of an edge $e$ in a graph $G$ is the set consisting of $e$ and of all edges having a common end vertex with $e$. Let $f$ be a mapping of the edge set $E\left(G\right)$ of $G$ into the set $\{-1,1\}$. If ${\sum }_{x\in N\left[e\right]}f\left(x\right)\ge 1$ for each $e\in E\left(G\right)$, then $f$ is called a signed edge dominating function on $G$. The minimum of the values ${\sum }_{x\in E\left(G\right)}f\left(x\right)$, taken over all signed edge dominating function $f$ on $G$, is called the signed edge domination number of $G$ and is...

We initiate the study of signed majority total domination in graphs. Let $G=(V,E)$ be a simple graph. For any real valued function $fV\to ℝ$ and $S\subseteq V$, let $f\left(S\right)={\sum }_{v\in S}f\left(v\right)$. A signed majority total dominating function is a function $fV\to \{-1,1\}$ such that $f\left(N\right(v\left)\right)\ge 1$ for at least a half of the vertices $v\in V$. The signed majority total domination number of a graph $G$ is ${\gamma }_{\mathrm{m}aj}^{\mathrm{t}}\left(G\right)=min\{f\left(V\right)\mid f$ is a signed majority total dominating function on $G\}$. We research some properties of the signed majority total domination number of a graph $G$ and obtain a few lower bounds of ${\gamma }_{\mathrm{m}aj}^{\mathrm{t}}\left(G\right)$.

By a signpost system we mean an ordered pair $(W,P)$, where $W$ is a finite nonempty set, $P\subseteq W\times W\times W$ and the following statements hold: $$\text{if}(u,v,w)\in P,\text{then}(v,u,u)\in P\text{and}(v,u,w)\notin P,\text{for}\text{all}u,v,w\in W;\text{if}u\ne v,i\text{then}\text{there}\text{exists}r\in W\text{such}\text{that}(u,r,v)\in P,\text{for}\text{all}u,v\in W.$$ We say that a signpost system $(W,P)$ is smooth if the folowing statement holds for all $u,v,x,y,z\in W$: if $(u,v,x),(u,v,z),(x,y,z)\in P$, then $(u,v,y)\in P$. We say thay a signpost system $(W,P)$ is simple if the following statement holds for all $u,v,x,y\in W$: if $(u,v,x),(x,y,v)\in P$, then $(u,v,y),(x,y,u)\in P$. By the underlying graph of a signpost system $(W,P)$ we mean the graph $G$ with $V\left(G\right)=W$ and such that the following statement holds for all distinct $u,v\in W$: $u$ and $v$ are adjacent in $G$ if and only if $(u,v,v)\in P$....

The paper reports the results of a search for pairs of groups of order $n$ that can be placed in the distance $n^2/4$ for the case when $n\in \{16,32\}$. The constructions that are used are of the general character and some of their properties are discussed as well.

Let G be a finite group of order n. The strong power graph Ps(G) of G is the undirected graph whose vertices are the elements of G such that two distinct vertices a and b are adjacent if am1=bm2 for some positive integers m1, m2 < n. In this article we classify all groups G for which Ps(G) is a line graph. Spectrum and permanent of the Laplacian matrix of the strong power graph Ps(G) are found for any finite group G.

In this paper we examine discrete functions that depend on their variables in a particular way, namely the H-functions. The results obtained in this work make the “construction” of these functions possible. H-functions are generalized, as well as their matrix representation by Latin hypercubes.