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 vertices with pendant vertices. We also characterize the graph which minimizes the Wiener index over the graphs on vertices with 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, . In this paper, we obtain the Wiener index of the tensor product of a path and a cycle.
We establish an exact formula for the word distance on the discrete Heisenberg group ℍ₃ with its standard set of generators. This formula is then used to prove the almost connectedness of the spheres for this distance.
Given a coloring of the vertices, we say subgraph H is monochromatic if every vertex of H is assigned the same color, and rainbow if no pair of vertices of H are assigned the same color. Given a graph G and a graph F, we define an F-WORM coloring of G as a coloring of the vertices of G without a rainbow or monochromatic subgraph H isomorphic to F. We present some results on this concept especially as regards to the existence, complexity, and optimization within certain graph classes. The focus is...
Given three planar graphs F,H, and G, an (F,H)-WORM coloring of G is a vertex coloring such that no subgraph isomorphic to F is rainbow and no subgraph isomorphic to H is monochromatic. If G has at least one (F,H)-WORM coloring, then W−F,H(G) denotes the minimum number of colors in an (F,H)-WORM coloring of G. We show that (a) W−F,H(G) ≤ 2 if |V (F)| ≥ 3 and H contains a cycle, (b) W−F,H(G) ≤ 3 if |V (F)| ≥ 4 and H is a forest with Δ (H) ≥ 3, (c) W−F,H(G) ≤ 4 if |V (F)| ≥ 5 and H is a forest with...