Abstract
Given a uniform probability r, 0 < r < 1, of selecting edges independently from a graph G, we define the edge cover probability polynomial EpðG; rÞ of G to be the probability of randomly selecting an edge cover of G. We provide general, and in some cases specific, formulas for obtaining EpðG; rÞ. We then demonstrate the existence of graphs which have either the largest or the smallest EpðG; rÞ within its class for all r. The classes we consider are trees, unicyclic graphs, and connected graphs having one more edge than the number of vertices. Thus we determine the optimal constructions with respect to edge covers within the context of these classes.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 538-547 |
| Number of pages | 10 |
| Journal | IEEE Transactions on Network Science and Engineering |
| Volume | 6 |
| Issue number | 3 |
| DOIs | |
| State | Published - Jul 1 2018 |
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Computer Science Applications
- Computer Networks and Communications