Examples of graphs that are rainbow domination regular and not vertex transitive are given. This answers two questions asked in Kuzman (2020). We also characterize all generalized Petersen graphs that are 3-rainbow domination regular.

Closeness is a measure of centrality, an important feature of communication and social networks. Extremal networks among all graphs and among several subclasses of graphs including trees and cacti are given. In addition, maximal graphs among cacti with fixed number of cycles and among cacti with given number of cut edges are provided.

Reliability Hosoya-Wiener polynomial for edge weighted graphs is defined, that can be used as a measure of reliability of a communication network. Each edge is assigned two weights, reliability and communication delay. Some basic properties are given and a recursive formula for the reliability Hosoya-Wiener polynomial of a rooted tree is proved that yields a linear time algorithm on weighted trees. On general graphs, the reliability Hosoya-Wiener polynomial can be computed in O( n 3 ) time.

The product graph B * F of graphs B and F is an interesting model in the design of large reliable networks. Fault tolerance and transmission delay of networks are important concepts in network design. The notions are strongly related to connectivity and diameter of a graph, and have been studied by many authors. Wide diameter of a graph combines studying connectivity with the diameter of a graph. Diameter with width k of a graph G, k-diameter, is defined as the minimum integer d for which there exist at least k internally disjoint paths of length at most d between any two distinct vertices in G. Denote by $\cal{D}^W_c (G)$ the c-diameter of G and κ(G) the connectivity of G. We prove that $\cal{D}^W_{a+b}(B * F) \le r_a(F) + \cal{D}^W_b (B) + 1$ for a ≤ κ(F) and b ≤ κ(B). The Rabin number r c (G) is the minimum integer d such that there are c internally disjoint paths of length at most d from any vertex v to any set of c vertices {v 1 , v 2 , ... , v c }.

In the frequency allocation problem, we are given a cellular telephone network whose geographical coverage area is divided into cells, where phone calls are serviced by frequencies assigned to them, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e. minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph, where every vertex knows its position in the graph. We present a 1-local 7/5-competitive distributed algorithm for multicoloring a hexagonal graph, thereby improving the previous 1-local 17/12-competitive algorithm.

A communication network can be modeled by a graph with weighted vertices and edges corresponding to the amount of traffic from sources and expected delays at links. We give a linear algorithm for computing the sum of all delays on a weighted cactus graphs. Cactus is a graph in which every edge lies on at most one cycle. The sum of delays is equivalent to the weighted Wiener number, a well known graph invariant in mathematical chemistry. Complexity of computing Wiener polynomial on cacti is discussed.