Monika M. Heinig, PhD

additional coauthors include: Giuseppe Pontillo, Camilla Russo, Enrico Tedeschi, Cinzia Valeria Russo, Teresa Costabile, Roberta Lanzillo, Arturo Brunetti, Vincenzo Brescia Morra

Abstract: Let G be a graph whose edges may fail, with equal but independent probability. When an edge fails, its endnodes are subverted and they and all edges incident on the endnodes are removed from the graph. If edges fail, and endnodes are subverted, the surviving subgraph is in a failure state if all components have order less than some predetermined threshold value. Neighbor component order connectivity is the minimum number of edges that must fail to create a failure state. In this work,… Show more

Abstract: Let G be a graph whose edges may fail, with equal but independent probability. When an edge fails, its endnodes are subverted and they and all edges incident on the endnodes are removed from the graph. If edges fail, and endnodes are subverted, the surviving subgraph is in a failure state if all components have order less than some predetermined threshold value. Neighbor component order connectivity is the minimum number of edges that must fail to create a failure state. In this work, we consider the reliability model associated with neighbor component order connectivity. Specifically, we consider the class of trees with a fixed number of numbers and investigate whether for a specific threshold value a tree exists which maximizes (or minimizes) the reliability "uniformity", i.e., for all possible probabilities of edge failure. Show less

Abstract: Consider a graph where edges can fail but nodes do not. However, when an edge fails, its endnodes are subverted, i.e., removed from the graph. Given a threshold value k >=1, the surviving subgraph produced by the failure of edges and the subversion of the endnodes of those edges is said to be in a failure state if all of its components have order <= k - 1. The minimum number of edge failures required to yield a failure state is called the neighbor component order edge… Show more

Abstract: Consider a graph where edges can fail but nodes do not. However, when an edge fails, its endnodes are subverted, i.e., removed from the graph. Given a threshold value k >=1, the surviving subgraph produced by the failure of edges and the subversion of the endnodes of those edges is said to be in a failure state if all of its components have order <= k - 1. The minimum number of edge failures required to yield a failure state is called the neighbor component order edge connectivity. It is the case that when k=1, the parameter is the size of a minimum edge cover of the nodes and k=2 is the edge domination number.

If the edges fail independently, all with the same probability 0 < r < 1, the unreliability of the graph is the probability that the surviving subgraph is in a failure state. A graph on n nodes with e edges is k-uniformly most reliable (k-UMR) provided its unreliability is minimum among all graphs in its class for all values of r and fixed k. k-Uniformly least reliable (k-ULR) graphs are defined analogously. We present k-UMR and k-ULR results for trees when k = 2. Show less

Abstract: If a spy network is modeled as a graph in which the nodes represent the spies and the edges are the communication links between spies, then consider the scenario where the interception of a link gives up both endnode spies. In graph-theoretic terms, edges fail and nodes do not, but when they do, the endnodes are subverted, i.e. they are removed. Given k > 0, we say that upon failure of some edges, the surviving subgraph is in an operating state if it has at least one component of… Show more

Abstract: If a spy network is modeled as a graph in which the nodes represent the spies and the edges are the communication links between spies, then consider the scenario where the interception of a link gives up both endnode spies. In graph-theoretic terms, edges fail and nodes do not, but when they do, the endnodes are subverted, i.e. they are removed. Given k > 0, we say that upon failure of some edges, the surviving subgraph is in an operating state if it has at least one component of order  k, and is in a failure state otherwise. The neighbor component order edge connectivity is the minimum number of edge failures required to create a failure state. We present some fundamental properties of this parameter and determine its value for certain types of graphs. Show less

Abstract: A corollary of the Kirchhoff matrix-tree theorem is used to find
the number of spanning trees of a graph via the roots of the characteristic
polynomial of the associated Laplacian matrix. Threshold graphs play a
role in bounding the number of spanning trees from below, given that the
number of nodes and edges are held fixed. Although other authors have
derived and developed the expression for the characteristic polynomial of
the Laplacian matrix of the threshold… Show more

Abstract: A corollary of the Kirchhoff matrix-tree theorem is used to find
the number of spanning trees of a graph via the roots of the characteristic
polynomial of the associated Laplacian matrix. Threshold graphs play a
role in bounding the number of spanning trees from below, given that the
number of nodes and edges are held fixed. Although other authors have
derived and developed the expression for the characteristic polynomial of
the Laplacian matrix of the threshold graph, we present here a different
algebraic approach due to Boesch. Show less

Abstract: The traditional vulnerability parameter connectivity is the minimum number of nodes needed to be removed to disconnect a network. Likewise, edge connectivity is the minimum number of edges needed to be removed to disconnect. A disconnected network may still be viable if it contains a sufficiently large component. Component order connectivity and component order edge connectivity are the minimum number of nodes, respectively edges needed to be removed so that all components of the… Show more

Abstract: The traditional vulnerability parameter connectivity is the minimum number of nodes needed to be removed to disconnect a network. Likewise, edge connectivity is the minimum number of edges needed to be removed to disconnect. A disconnected network may still be viable if it contains a sufficiently large component. Component order connectivity and component order edge connectivity are the minimum number of nodes, respectively edges needed to be removed so that all components of the resulting network have order less than some preassigned threshold value. In this paper we survey some results of the component order connectivity models. Show less

Abstract: A multigraph is Laplacian Integral if the eigenvalues of its associated Laplacian matrix are all integers. We consider one type of Laplacian integral multigraph whose underlying graph is complete, as well as a proof that it maximizes the number of spanning trees among all multigraphs having the same number of nodes and edges. We also present some examples of Laplacian integral multigraphs, including an entire class of multigraphs having an underlying graph which is proper threshold.