The distance spectral radius ρ(G) of a graph G is the largest eigenvalue of the distance matrix D(G). Let U (n,m) be the class of unicyclic graphs of order n with given matching number m (m ≠ 3). In this paper, we determine the extremal unicyclic graph which has minimal distance spectral radius in U (n,m) Cn.

For two vertices $u$ and $v$ of a graph $G$, the closed interval $I[u,v]$ consists of $u$, $v$, and all vertices lying in some $u\text{--}v$ geodesic of $G$, while for $S\subseteq V\left(G\right)$, the set $I\left[S\right]$ is the union of all sets $I[u,v]$ for $u,v\in S$. A set $S$ of vertices of $G$ for which $I\left[S\right]=V\left(G\right)$ is a geodetic set for $G$, and the minimum cardinality of a geodetic set is the geodetic number $g\left(G\right)$. A vertex $v$ in $G$ is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in $G$ is its extreme order $\mathrm{e}x\left(G\right)$. A graph $G$ is an extreme geodesic...

For a nontrivial connected graph $F$, the $F$-degree of a vertex $v$ in a graph $G$ is the number of copies of $F$ in $G$ containing $v$. A graph $G$ is $F$-continuous (or $F$-degree continuous) if the $F$-degrees of every two adjacent vertices of $G$ differ by at most 1. All $P_3$-continuous graphs are determined. It is observed that if $G$ is a nontrivial connected graph that is $F$-continuous for all nontrivial connected graphs $F$, then either $G$ is regular or $G$ is a path. In the case of a 2-connected graph $F$, however, there...

The paper deals with the decomposition and with the boundarz and hull construction of the so-called nondense point set. This problem and its applications have been frequently studied in computational geometry, raster graphics and, in particular, in the image processing (see e.g. [3], [6], [7], [8], [9], [10]). We solve a problem of the point set decomposition by means of certain relations in graph theory.

Let G = (V,E) be a connected graph and let k be a positive integer with k ≤ rad(G). A subset D ⊆ V is called a distance k-dominating set of G if for every v ∈ V - D, there exists a vertex u ∈ D such that d(u,v) ≤ k. In this paper we study the fractional version of distance k-domination and related parameters.

In a graph G, the distance d(u,v) between a pair of vertices u and v is the length of a shortest path joining them. The eccentricity e(u) of a vertex u is the distance to a vertex farthest from u. The minimum eccentricity is called the radius of the graph and the maximum eccentricity is called the diameter of the graph. The radial graph R(G) based on G has the vertex set as in G, two vertices u and v are adjacent in R(G) if the distance between them in G is equal to the radius of G. If G is disconnected,...

For two vertices u and v of a graph G, the closed interval I[u,v] consists of u, v, and all vertices lying in some u-v geodesic in G. If S is a set of vertices of G, then I[S] is the union of all sets I[u,v] for u, v ∈ S. If I[S] = V(G), then S is a geodetic set for G. The geodetic number g(G) is the minimum cardinality of a geodetic set. A set S of vertices in a graph G is uniform if the distance between every two distinct vertices of S is the same fixed number. A geodetic set is essential if for...

Systems of consistent linear equations with symmetric positive semidefinite matrices arise naturally while solving many scientific and engineering problems. In case of a "floating" static structure, the boundary conditions are not sufficient to prevent its rigid body motions. Traditional solvers based on Cholesky decomposition can be adapted to these systems by recognition of zero rows or columns and also by setting up a well conditioned regular submatrix of the problem that...

Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that $DomDo{m}_u=Dom{₂}_u$ holds for ${}_u$ = all connected graphs without induced $P_u$ (u ≥ 2). (In particular, ₂ = K₁ and...

For any $n\ge 1$ and any $k\ge 1$, a graph $S(n,k)$ is introduced. Vertices of $S(n,k)$ are $n$-tuples over $\{1,2,...,k\}$ and two $n$-tuples are adjacent if they are in a certain relation. These graphs are graphs of a particular variant of the Tower of Hanoi problem. Namely, the graphs $S(n,3)$ are isomorphic to the graphs of the Tower of Hanoi problem. It is proved that there are at most two shortest paths between any two vertices of $S(n,k)$. Together with a formula for the distance, this result is used to compute the distance between two vertices in...

For a connected graph G = (V,E), a set D ⊆ V(G) is a dominating set of G if every vertex in V(G)-D has at least one neighbour in D. The distance $d_G(u,v)$ between two vertices u and v is the length of a shortest (u-v) path in G. An (u-v) path of length $d_G(u,v)$ is called an (u-v)-geodesic. A set X ⊆ V(G) is convex in G if vertices from all (a-b)-geodesics belong to X for any two vertices a,b ∈ X. A set X is a convex dominating set if it is convex and dominating. The convex domination number ${\gamma }_{con}\left(G\right)$ of a graph G is the...

Let G = (V,E) be a graph. The distance between two vertices u and v in a connected graph G is the length of the shortest (u-v) path in G. A set D ⊆ V(G) is a dominating set if every vertex of G is at distance at most 1 from an element of D. The domination number of G is the minimum cardinality of a dominating set of G. A set D ⊆ V(G) is a 2-distance dominating set if every vertex of G is at distance at most 2 from an element of D. The 2-distance domination number of G is the minimum cardinality...

The additive stretch number $s_{add}\left(G\right)$ of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with $s_{add}\left(G\right)\le k$ for some k ∈ N₀ = 0,1,2,.... Furthermore, we derive characterizations of these classes for k = 1 and k = 2.