Combinatorics and Graph Theory


Tree-3-Cover Ratio of Graphs: Asymptotes and Areas

Authors: Paul August Winter

The graph theoretical ratio, the tree-cover ratio, involving spanning trees of a graph G, and a 2-vertex covering (a minimum set S of vertices such that every edge (or path on 2 vertices) of G has at least vertex end in S) of G has been researched. In this paper we introduce a ratio, called the tree-3-covering ratio with respect to S, involving spanning trees and a 3-vertex covering (a minimum set S of vertices of G such that every path on 3 vertices has at least one vertex in S) of graphs. We discuss the asymptotic convergence of this tree-3-cover ratio for classes of graphs, which may have application in ideal communication situations involving spanning trees and 3-vertex coverings of extreme networks. We show that this asymptote lies on the interval with the dumbbell graph (a complete graph on n-1 vertices appended to an end vertex) has tree-3-cover asymptotic convergence of 1/e, identical to the convergence in the secretary problem, and the tree-cover asymptotic convergence of complete graphs. We also introduce the idea of a tree-3-cover area by integrating this tree-3-cover ratio. AMS classification: 05C99 Key words: spanning trees of graphs, vertex cover, 3-vertex cover, ratios, social interaction, network communication, convergence, asymptotes.

Comments: 18 Pages.

Download: PDF

Submission history

[v1] 2015-03-16 04:59:31

Unique-IP document downloads: 50 times

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus