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

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.

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.

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 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 two vertices u and v of a connected graph G, the set $I_G[u,v]$ consists of all those vertices lying on u-v geodesics in G. Given a set S of vertices of G, the union of all sets $I_G[u,v]$ for u,v ∈ S is denoted by $I_G\left[S\right]$. A set S ⊆ V(G) is a geodetic set if $I_G\left[S\right]=V\left(G\right)$ and the minimum cardinality of a geodetic set is its geodetic number g(G) of G. Bounds for the geodetic number of strong product graphs are obtainted and for several classes improved bounds and exact values are obtained.

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

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