Search

A k-clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a k-clique covering is called the local clique cover number of G and is denoted by lcc(G). Local clique cover number can be viewed as the local counterpart of the clique cover number that is equal to the minimum total number of cliques covering all edges. In this article, several aspects of the local clique covering problem are studied and its relationships to other well-known problems are discussed. In particular, it is proved that the local clique cover number of every claw-free graph is at most cΔ/ logΔ, where Δ is the maximum degree of the graph and c is a constant. It is also shown that the bound is tight, up to a constant factor. Moreover, regarding a conjecture by Chen et al. (Clique covering the edges of a locally cobipartite graph, Discrete Math 219(1-3)(2000), 17-26), we prove that the clique cover number of every connected claw-free graph on n vertices with the minimum degree δ, is at most n + c δ4/3 log1/3 δ, where c is a constant. [ABSTRACT FROM AUTHOR]

Routing methods for optimal distribution of traffic in data networks that can also provide quality of service (QoS) for users is one of the challenges in recent years' research on next generation networks. The major QoS requirement in most cases is an upper bound on end-to-end path delay. In multipath virtual circuit switched networks each session distributes its traffic among a set of available paths. If all possible paths are considered available, then the source's decision on its traffic distribution can be considered as routing. A model of the routing function as a mathematical problem which distributes the input traffic over possible paths for each session is proposed here. A distributed and iterative algorithm which will keep the average end-to-end delay for individual paths below a required bound is introduced. This algorithm minimizes the total average delay of all packets in the network. The convergence of the algorithm is illustrated. [ABSTRACT FROM AUTHOR]