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.

A graph G is called (H;k)-vertex stable if G contains a subgraph isomorphic to H ever after removing any of its k vertices. Q(H;k) denotes the minimum size among the sizes of all (H;k)-vertex stable graphs. In this paper we complete the characterization of $(K_{m,n};1)$-vertex stable graphs with minimum size. Namely, we prove that for m ≥ 2 and n ≥ m+2, $Q(K_{m,n};1)=mn+m+n$ and $K_{m,n}*K₁$ as well as $K_{m+1,n+1}-e$ are the only $(K_{m,n};1)$-vertex stable graphs with minimum size, confirming the conjecture of Dudek and Zwonek.

A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.

A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth of the...

We introduce weakly strongly quasi-primary (briefly, wsq-primary) ideals in commutative rings. Let $R$ be a commutative ring with a nonzero identity and $Q$ a proper ideal of $R$. The proper ideal $Q$ is said to be a weakly strongly quasi-primary ideal if whenever $0\ne ab\in Q$ for some $a,b\in R$, then $a^2\in Q$ or $b\in \sqrt{Q}.$ Many examples and properties of wsq-primary ideals are given. Also, we characterize nonlocal Noetherian von Neumann regular rings, fields, nonlocal rings over which every proper ideal is wsq-primary, and zero dimensional...

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

Let G be a graph of order n and size m. A γ-labeling of G is a one-to-one function f:V(G) → 0,1,2,...,m that induces a labeling f’: E(G) → 1,2,...,m of the edges of G defined by f’(e) = |f(u)-f(v)| for each edge e = uv of G. The value of a γ-labeling f is $val\left(f\right)={\Sigma }_{e\in E\left(G\right)}{f}^{\text{'}}K\left(e\right)$. The maximum value of a γ-labeling of G is defined as $va{l}_{max}\left(G\right)=maxval\left(f\right):fisa\gamma -labelingofG$; while the minimum value of a γ-labeling of G is $va{l}_{min}\left(G\right)=minval\left(f\right):fisa\gamma -labelingofG$; The values $va{l}_{max}\left(S_{p,q}\right)$ and $va{l}_{min}\left(S_{p,q}\right)$ are determined for double stars $S_{p,q}$. We present characterizations of connected graphs G of order n for which $va{l}_{min}\left(G\right)=n$ or $va{l}_{min}\left(G\right)=n+1$.

The Θ-graph Θ(G) of a partial cube G is the intersection graph of the equivalence classes of the Djoković-Winkler relation. Θ-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, Θ(G) is complete if and only if G can be obtained from K₁ by a sequence of (newly introduced) dense expansions. Θ-graphs are also compared with familiar concepts of crossing graphs and τ-graphs.

Let P denote a 3-uniform hypergraph consisting of 7 vertices a, b, c, d, e, f, g and 3 edges {a, b, c}, {c, d, e}, and {e, f, g}. It is known that the r-color Ramsey number for P is R(P; r) = r + 6 for r ≤ 9. The proof of this result relies on a careful analysis of the Turán numbers for P. In this paper, we refine this analysis further and compute the fifth order Turán number for P, for all n. Using this number for n = 16, we confirm the formula R(P; 10) = 16.

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