By a ternary structure we mean an ordered pair $(X_0,T_0)$, where $X_0$ is a finite nonempty set and $T_0$ is a ternary relation on $X_0$. By the underlying graph of a ternary structure $(X_0,T_0)$ we mean the (undirected) graph $G$ with the properties that $X_0$ is its vertex set and distinct vertices $u$ and $v$ of $G$ are adjacent if and only if $$\{x\in X_0{T}_0(u,x,v)\}\cup \{x\in X_0{T}_0(v,x,u)\}=\{u,v\}.$$ A ternary structure $(X_0,T_0)$ is said to be the B-structure of a connected graph $G$ if $X_0$ is the vertex set of $G$ and the following statement holds for all $u,x,y\in X_0$: $T_0(x,u,y)$ if and only if $u$ belongs to an...

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V,E_N)$ where $E_N$ = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph $N^k\left(G\right):=N\left(N(...N\left(G\right))\right)$ of G. In particular we investigate conditions for G and k such that $N^k\left(G\right)$ becomes a complete graph.

For a given graph G and a positive integer r the r-path graph, $P_r\left(G\right)$, has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let $P_r^k\left(G\right)$ be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of $P_r^k\left(G\right)$. The k-history $P_r^{-k}\left(H\right)$ is a subgraph of G that is induced by all edges that take part in the recursive...

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition $N_G\left(x\right)\subseteq N_G\left[u\right]\cup N_G\left[v\right]$, where $N_G\left[x\right]=N_G\left(x\right)\cup x$. In the case where G is a claw-free graph, G* is equal to G². We define $\sigma °ₜ=min{\sum }_{x\in S}{d}_G\left(x\right):SisanindependentsetinG*and\left|S\right|=t$. We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

Let $G=(V,E)$ be a simple graph. A $3$-valued function $fV\left(G\right)\to \{-1,0,1\}$ is said to be a minus dominating function if for every vertex $v\in V$, $f\left(N\left[v\right]\right)={\sum }_{u\in N\left[v\right]}f\left(u\right)\ge 1$, where $N\left[v\right]$ is the closed neighborhood of $v$. The weight of a minus dominating function $f$ on $G$ is $f\left(V\right)={\sum }_{v\in V}f\left(v\right)$. The minus domination number of a graph $G$, denoted by ${\gamma }^{-}\left(G\right)$, equals the minimum weight of a minus dominating function on $G$. In this paper, the following two results are obtained. (1) If $G$ is a bipartite graph of order $n$, then $${\gamma }^{-}\left(G\right)\ge 4\left(\sqrt{n+1}-1\right)-n.$$ (2) For any negative integer $k$ and any positive integer...

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class $C_f$ of all finite undirected graphs. If G is a graph from $C_f$, then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

A graph $G$ is a $\{d,d+k\}$-graph, if one vertex has degree $d+k$ and the remaining vertices of $G$ have degree $d$. In the special case of $k=0$, the graph $G$ is $d$-regular. Let $k,p\ge 0$ and $d,n\ge 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected $\{d,d+k\}$-graph of order $n$ without a matching $M$ of size $2\left|M\right|=n-p$, then we show in this paper the following: If $d=2$, then $k\ge 2(p+2)$ and (i) $n\ge k+p+6$. If $d\ge 3$ is odd and $t$ an integer with $1\le t\le p+2$, then (ii) $n\ge d+k+1$ for $k\ge d(p+2)$, (iii) $n\ge d(p+3)+2t+1$ for $d(p+2-t)+t\le k\le d(p+3-t)+t-3$, (iv) $n\ge d(p+3)+2p+7$ for $k\le p$. If $d\ge 4$ is even, then (v) $n\ge d+k+2-\eta$ for $k\ge d(p+3)+p+4+\eta$, (vi) $n\ge d+k+p+2-2t=d(p+4)+p+6$ for $k=d(p+3)+4+2t$ and $p\ge 1$,...

In this paper, we consider the intersection graph $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$ of gamma sets in the total graph on ℤₙ. We characterize the values of n for which $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$ is complete, bipartite, cycle, chordal and planar. Further, we prove that $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$ is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$.

We extend the notion of a potentially H-graphic sequence as follows. Let A and B be nonnegative integer sequences. The sequence pair S = (A,B) is said to be bigraphic if there is some bipartite graph G = (X ∪ Y,E) such that A and B are the degrees of the vertices in X and Y, respectively. If S is a bigraphic pair, let σ(S) denote the sum of the terms in A. Given a bigraphic pair S, and a fixed bipartite graph H, we say that S is potentially H-bigraphic if there is some realization of...

We construct a locally compact Hausdorff topology on the path space of a finitely aligned k-graph Λ. We identify the boundary-path space ∂Λ as the spectrum of a commutative C*-subalgebra $D_{\Lambda }$ of C*(Λ). Then, using a construction similar to that of Farthing, we construct a finitely aligned k-graph Λ̃ with no sources in which Λ is embedded, and show that ∂Λ is homeomorphic to a subset of ∂Λ̃. We show that when Λ is row-finite, we can identify C*(Λ) with a full corner of C*(Λ̃), and deduce...