Currently displaying 1 – 20 of 51

Showing per page

Order by Relevance | Title | Year of publication

Connected graphs containing a given connected graph as a unique greatest common subgraph.

Aequationes mathematicae

On graphs with a unique minimum hull set

Discussiones Mathematicae Graph Theory

We show that for every integer k ≥ 2 and every k graphs G₁,G₂,...,Gₖ, there exists a hull graph with k hull vertices v₁,v₂,...,vₖ such that link $L\left({v}_{i}\right)={G}_{i}$ for 1 ≤ i ≤ k. Moreover, every pair a, b of integers with 2 ≤ a ≤ b is realizable as the hull number and geodetic number (or upper geodetic number) of a hull graph. We also show that every pair a,b of integers with a ≥ 2 and b ≥ 0 is realizable as the hull number and forcing geodetic number of a hull graph.

The forcing geodetic number of a graph

Discussiones Mathematicae Graph Theory

For two vertices u and v of a graph G, the set I(u, v) consists of all vertices lying on 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. A set S is a geodetic set if I(S) = V(G). A minimum geodetic set is a geodetic set of minimum cardinality and this cardinality is the geodetic number g(G). A subset T of a minimum geodetic set S is called a forcing subset for S if S is the unique minimum geodetic set containing T. The forcing geodetic...

The existence of 2-factors in squares of graphs

Czechoslovak Mathematical Journal

The forcing convexity number of a graph

Czechoslovak Mathematical Journal

For two vertices $u$ and $v$ of a connected graph $G$, the set $I\left(u,v\right)$ consists of all those vertices lying on a $u$$v$ geodesic in $G$. For a set $S$ of vertices of $G$, the union of all sets $I\left(u,v\right)$ for $u,v\in S$ is denoted by $I\left(S\right)$. A set $S$ is a convex set if $I\left(S\right)=S$. The convexity number $\mathrm{c}on\left(G\right)$ of $G$ is the maximum cardinality of a proper convex set of $G$. A convex set $S$ in $G$ with $|S|=\mathrm{c}on\left(G\right)$ is called a maximum convex set. A subset $T$ of a maximum convex set $S$ of a connected graph $G$ is called a forcing subset for $S$ if $S$ is the unique maximum convex set...

Extreme geodesic graphs

Czechoslovak Mathematical Journal

For two vertices $u$ and $v$ of a graph $G$, the closed interval $I\left[u,v\right]$ 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\left[u,v\right]$ 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...

$H$-convex graphs

Mathematica Bohemica

For two vertices $u$ and $v$ in a connected graph $G$, the set $I\left(u,v\right)$ consists of all those vertices lying on a $u-v$ geodesic in $G$. For a set $S$ of vertices of $G$, the union of all sets $I\left(u,v\right)$ for $u,v\in S$ is denoted by $I\left(S\right)$. A set $S$ is convex if $I\left(S\right)=S$. The convexity number $\mathrm{c}on\left(G\right)$ is the maximum cardinality of a proper convex set in $G$. A convex set $S$ is maximum if $|S|=\mathrm{c}on\left(G\right)$. The cardinality of a maximum convex set in a graph $G$ is the convexity number of $G$. For a nontrivial connected graph $H$, a connected graph $G$ is an $H$-convex graph if $G$ contains...

The forcing dimension of a graph

Mathematica Bohemica

For an ordered set $W=\left\{{w}_{1},{w}_{2},\cdots ,{w}_{k}\right\}$ of vertices and a vertex $v$ in a connected graph $G$, the (metric) representation of $v$ with respect to $W$ is the $k$-vector $r\left(v|W\right)$ = ($d\left(v,{w}_{1}\right),d\left(v,{w}_{2}\right),\cdots ,d\left(v,{w}_{k}\right)$), where $d\left(x,y\right)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations. A resolving set of minimum cardinality is a basis for $G$ and the number of vertices in a basis is its (metric) dimension $dim\left(G\right)$. For a basis $W$ of $G$, a subset $S$ of $W$ is called a forcing subset of $W$ if $W$ is...

On Regular Bipartite-Preserving Supergraphs. (Short Communication).

Aequationes mathematicae

On Hamiltonian properties of powers of special Hamiltonian graphs

Colloquium Mathematicae

Geodetic sets in graphs

Discussiones Mathematicae Graph Theory

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

Distance defined by spanning trees in graphs

Discussiones Mathematicae Graph Theory

For a spanning tree T in a nontrivial connected graph G and for vertices u and v in G, there exists a unique u-v path u = u₀, u₁, u₂,..., uₖ = v in T. A u-v T-path in G is a u- v path u = v₀, v₁,...,vₗ = v in G that is a subsequence of the sequence u = u₀, u₁, u₂,..., uₖ = v. A u-v T-path of minimum length is a u-v T-geodesic in G. The T-distance ${d}_{G|T}\left(u,v\right)$ from u to v in G is the length of a u-v T-geodesic. Let geo(G) and geo(G|T) be the set of geodesics and the set of T-geodesics respectively in G. Necessary...

Page 1 Next