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 $(0,2)$-graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $(0,\lambda )$-graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $(0,2)$-graph. $(0,2)$-graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in $(0,\lambda )$-graphs and more specifically...

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number ${\gamma }_{\times k}\left(G\right)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $|N_G\left[v\right]\cap S|\ge k$. Also the total k-domination number ${\gamma }_{\times k,t}\left(G\right)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $|N_G\left(v\right)\cap S|\ge k$. The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for...

Let be a set of graphs and for a graph G let ${\alpha }_{}\left(G\right)$ and $\alpha {*}_{}\left(G\right)$ denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on ${\alpha }_{}\left(G\right)$ and $\alpha {*}_{}\left(G\right)$ are presented.

For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: $K_{2,2,r}$ r ∈ 4,5,6,7,8, $K_{2,3,4}$, $K_{1*4,4}$, $K_{1*4,5}$, $K_{1*5,4}$. Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for $K_{2,2,r}$ r ∈ 4,5,6,7,8, the others have been proved not...

A graph is called distance integral (or $D$-integral) if all eigenvalues of its distance matrix are integers. In their study of $D$-integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$-integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_1,p_2,p_3}$ with $p_1<p_2<p_3$, and $K_{p_1,p_2,p_3,p_4}$ with $p_1<p_2<p_3<p_4$, as well as the infinite classes of distance integral...

The paired domination number ${\gamma }_{pr}\left(G\right)$ of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: ${\gamma }_{pr}\left(\pi G\right)=2{\gamma }_{pr}\left(G\right)$ for all πG; ${\gamma }_{pr}\left(K₂☐G\right)=2{\gamma }_{pr}\left(G\right)$; ${\gamma }_{pr}\left(K₂☐G\right)={\gamma }_{pr}\left(G\right)$.

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

The domination subdivision number $s{d}_{\gamma }\left(G\right)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

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

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.

A Roman dominating function on a graph G is a function f:V(G) → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value $f\left(V\left(G\right)\right)={\sum }_{u\in V\left(G\right)}f\left(u\right)$. The Roman domination number, ${\gamma }_R\left(G\right)$, of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_R\left(G\right)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G)...

The oriented chromatic number of an oriented graph ${}^{\to }G$ is the minimum order of an oriented graph ${}^{\to }H$ such that ${}^{\to }G$ admits a homomorphism to ${}^{\to }H$. The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph ${}^{\to }U$ such that every orientation ${}^{\to }G$ of G admits a homomorphism to ${}^{\to }U$. We give...

Let $G$ be a $k$-connected graph with $k\ge 2$. A hinge is a subset of $k$ vertices whose deletion from $G$ yields a disconnected graph. We consider the algebraic connectivity and Fiedler vectors of such graphs, paying special attention to the signs of the entries in Fiedler vectors corresponding to vertices in a hinge, and to vertices in the connected components at a hinge. The results extend those in Fiedler’s papers Algebraic connectivity of graphs (1973), A property of eigenvectors of nonnegative...