The Edge Cover Probability Polynomial of a Graph and Optimal Network Construction

Michael Yatauro

doi:10.1109/TNSE.2018.2820062

The Edge Cover Probability Polynomial of a Graph and Optimal Network Construction

Michael Yatauro

Penn State Brandywine

Research output: Contribution to journal › Article › peer-review

Abstract

Given a uniform probability <formula><tex>$\rho, 0 < \rho < 1$</tex></formula>, of selecting edges independently from a graph <formula><tex>$G$</tex></formula>, we define the edge cover probability polynomial <formula><tex>$Ep(G, \rho)$</tex></formula> of <formula><tex>$G$</tex></formula> to be the probability of randomly selecting an edge cover of <formula><tex>$G$</tex></formula>. We provide general, and in some cases specific, formulas for obtaining <formula><tex>$Ep(G, \rho)$</tex></formula>. We then demonstrate the existence of graphs which have either the largest or the smallest <formula><tex>$Ep(G, \rho)$</tex></formula> within its class for all ρ. 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)
Journal	IEEE Transactions on Network Science and Engineering
DOIs	https://doi.org/10.1109/TNSE.2018.2820062
State	Accepted/In press - Mar 26 2018

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Computer Science Applications
Computer Networks and Communications

Access to Document

10.1109/TNSE.2018.2820062

Cite this

@article{986414982059441789add219c386c079,

title = "The Edge Cover Probability Polynomial of a Graph and Optimal Network Construction",

abstract = "Given a uniform probability $\rho, 0 < \rho < 1$, of selecting edges independently from a graph $G$, we define the edge cover probability polynomial $Ep(G, \rho)$ 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, \rho)$. We then demonstrate the existence of graphs which have either the largest or the smallest $Ep(G, \rho)$ within its class for all ρ. 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.",

author = "Michael Yatauro",

year = "2018",

month = mar,

day = "26",

doi = "10.1109/TNSE.2018.2820062",

language = "English (US)",

journal = "IEEE Transactions on Network Science and Engineering",

issn = "2327-4697",

publisher = "IEEE Computer Society",

}

TY - JOUR

T1 - The Edge Cover Probability Polynomial of a Graph and Optimal Network Construction

AU - Yatauro, Michael

PY - 2018/3/26

Y1 - 2018/3/26

N2 - Given a uniform probability $\rho, 0 < \rho < 1$, of selecting edges independently from a graph $G$, we define the edge cover probability polynomial $Ep(G, \rho)$ 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, \rho)$. We then demonstrate the existence of graphs which have either the largest or the smallest $Ep(G, \rho)$ within its class for all ρ. 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.

AB - Given a uniform probability $\rho, 0 < \rho < 1$, of selecting edges independently from a graph $G$, we define the edge cover probability polynomial $Ep(G, \rho)$ 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, \rho)$. We then demonstrate the existence of graphs which have either the largest or the smallest $Ep(G, \rho)$ within its class for all ρ. 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.

UR - http://www.scopus.com/inward/record.url?scp=85044854391&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044854391&partnerID=8YFLogxK

U2 - 10.1109/TNSE.2018.2820062

DO - 10.1109/TNSE.2018.2820062

M3 - Article

AN - SCOPUS:85044854391

SN - 2327-4697

JO - IEEE Transactions on Network Science and Engineering

JF - IEEE Transactions on Network Science and Engineering

ER -

The Edge Cover Probability Polynomial of a Graph and Optimal Network Construction

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this