In this paper, by a travel groupoid is meant an ordered pair $(V,*)$ such that $V$ is a nonempty set and $*$ is a binary operation on $V$ satisfying the following two conditions for all $u,v\in V$: $$(u*v)*u=u;\text{if}(u*v)*v=u,\text{then}u=v.$$ Let $(V,*)$ be a travel groupoid. It is easy to show that if $x,y\in V$, then $x*y=y$ if and only if $y*x=x$. We say that $(V,*)$ is on a (finite or infinite) graph $G$ if $V\left(G\right)=V$ and $$E\left(G\right)=\left\{\right\{u,v\}u,v\in V\text{and}u\ne u*v=v\}.$$ Clearly, every travel groupoid is on exactly one graph. In this paper, some properties of travel groupoids on graphs are studied.

The notion of travel groupoids was introduced by L. Nebeský in 2006 in connection with a study on geodetic graphs. A travel groupoid is a pair of a set $V$ and a binary operation $*$ on $V$ satisfying two axioms. We can associate a graph with a travel groupoid. We say that a graph $G$ has a travel groupoid if the graph associated with the travel groupoid is equal to $G$. Nebeský gave a characterization of finite graphs having a travel groupoid. In this paper, we study travel groupoids on infinite graphs....

Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like...

Tree-like partial cubes were introduced in [B. Brešar, W. Imrich, S. Klavžar, Tree-like isometric subgraphs of hypercubes, Discuss. Math. Graph Theory, 23 (2003), 227-240] as a generalization of median graphs. We present some incorrectnesses from that article. In particular we point to a gap in the proof of the theorem about the dismantlability of the cube graph of a tree-like partial cube and give a new proof of that result, which holds also for a bigger class of graphs, so called tree-like partial...

We prove that every triangle-free planar graph with minimum degree 3 has radius at least 3; equivalently, no vertex neighborhood is a dominating set.

A graph $G$ is called an $S$-graph if its periphery $Peri\left(G\right)$ is equal to its center eccentric vertices $Cep\left(G\right)$. Further, a graph $G$ is called a $D$-graph if $Peri\left(G\right)\cap Cep\left(G\right)=\varnothing$. We describe $S$-graphs and $D$-graphs for small radius. Then, for a given graph $H$ and natural numbers $r\ge 2$, $n\ge 2$, we construct an $S$-graph of radius $r$ having $n$ central vertices and containing $H$ as an induced subgraph. We prove an analogous existence theorem for $D$-graphs, too. At the end, we give some properties of $S$-graphs and $D$-graphs.

Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V (G) can be correctly...

A vertex v ∈ V (G) is said to distinguish two vertices x, y ∈ V (G) of a graph G if the distance from v to x is di erent from the distance from v to y. A set W ⊆ V (G) is a total resolving set for a graph G if for every pair of vertices x, y ∈ V (G), there exists some vertex w ∈ W − {x, y} which distinguishes x and y, while W is a weak total resolving set if for every x ∈ V (G)−W and y ∈ W, there exists some w ∈ W −{y} which distinguishes x and y. A weak total resolving set of minimum cardinality...

The Wiener index of a connected graph G, denoted by W(G), is defined as $½{\sum }_{u,v\in V\left(G\right)}{d}_G(u,v)$. Similarly, the hyper-Wiener index of a connected graph G, denoted by WW(G), is defined as $½W\left(G\right)+¼{\sum }_{u,v\in V\left(G\right)}d{²}_G(u,v)$. The vertex Padmakar-Ivan (vertex PI) index of a graph G is the sum over all edges uv of G of the number of vertices which are not equidistant from u and v. In this paper, the exact formulae for Wiener, hyper-Wiener and vertex PI indices of the strong product $G⊠K_{m₀,m₁,...,m_{r-1}}$, where $K_{m₀,m₁,...,m_{r-1}}$ is the complete multipartite graph with partite sets of sizes...

The Wiener index, W, is the sum of distances between all pairs of vertices in a graph G. The quadratic line graph is defined as L(L(G)), where L(G) is the line graph of G. A generalized star S is a tree consisting of Δ ≥ 3 paths with the unique common endvertex. A relation between the Wiener index of S and of its quadratic graph is presented. It is shown that generalized stars having the property W(S) = W(L(L(S)) exist only for 4 ≤ Δ ≤ 6. Infinite families of generalized stars with this property...

The Wiener index of a connected graph is defined as the sum of the distances between all unordered pairs of its vertices. We characterize the graphs which extremize the Wiener index among all graphs on $n$ vertices with $k$ pendant vertices. We also characterize the graph which minimizes the Wiener index over the graphs on $n$ vertices with $s$ cut-vertices.

The Wiener index, denoted by W(G), of a connected graph G is the sum of all pairwise distances of vertices of the graph, that is, $W\left(G\right)=½{\Sigma }_{u,v\in V\left(G\right)}d(u,v)$. In this paper, we obtain the Wiener index of the tensor product of a path and a cycle.