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

A graph property is any isomorphism closed class of simple graphs. For a simple finite graph H, let → H denote the class of all simple countable graphs that admit homomorphisms to H, such classes of graphs are called hom-properties. Given a graph property 𝓟, a graph G ∈ 𝓟 is universal in 𝓟 if each member of 𝓟 is isomorphic to an induced subgraph of G. In particular, we consider universal graphs in → H and we give a new proof of the existence of a universal graph in → H, for any finite graph...

For a fixed positive integer $k$ and $G=(V,E)$ a connected graph of order $n$, whose minimum vertex degree is at least $k$, a set $S\subseteq V$ is a total $k$-dominating set, also known as a $k$-tuple total dominating set, if every vertex $v\in V$ has at least $k$ neighbors in $S$. The minimum size of a total $k$-dominating set for $G$ is called the total $k$-domination number of $G$, denoted by ${\gamma }_{kt}\left(G\right)$. The total $k$-domination problem is to determine a minimum total $k$-dominating set of $G$. Since the exact problem is in general quite difficult to solve,...

For a connected graph $G$ of order $n\ge 2$ and a linear ordering $s:v_1,v_2,...,v_n$ of vertices of $G$, $d\left(s\right)={\sum }_{i=1}^{n-1}d(v_i,v_{i+1})$, where $d(v_i,v_{i+1})$ is the distance between $v_i$ and $v_{i+1}$. The upper traceable number $t^{+}\left(G\right)$ of $G$ is $t^{+}\left(G\right)=max\left\{d\left(s\right)\right\}$, where the maximum is taken over all linear orderings $s$ of vertices of $G$. It is known that if $T$ is a tree of order $n\ge 3$, then $2n-3\le t^{+}\left(T\right)\le \lfloor n^2/2\rfloor -1$ and $t^{+}\left(T\right)\le \lfloor n^2/2\rfloor -3$ if $T\ne P_n$. All pairs $n,k$ for which there exists a tree $T$ of order $n$ and $t^{+}\left(T\right)=k$ are determined and a characterization of all those trees of order $n\ge 4$ with upper traceable number $\lfloor n^2/2\rfloor -3$ is established. For a connected graph $G$ of order...

Recent model of lifetime after a heart attack involves some integer coefficients. Our goal is to get these coefficients in simple way and transparent form. To this aim we construct a schema according to a rule which combines the ideas used in the Pascal triangle and the generalized Fibonacci and Lucas numbers

In this paper, we introduce the notion of a variety of graphs closed under isomorphic images, subgraph identifications and induced subgraphs (induced connected subgraphs) firstly and next closed under isomorphic images, subgraph identifications, circuits and cliques. The structure of the corresponding lattices is investigated.

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