You are here
Search results
(1  2 of 2)
 Title
 Distancepreserving graphs
 Creator
 Nussbaum, Ronald
 Date
 2014
 Collection
 Electronic Theses & Dissertations
 Description

Let G be a simple graph on n vertices, where d_G(u,v) denotes the distance between vertices u and v in G. An induced subgraph H of G is isometric if d_H(u,v)=d_G(u,v) for all u,v in V(H). We say that G is a distancepreserving graph if G contains at least one isometric subgraph of order k for every k where 1<=k<=n.A number of sufficient conditions exist for a graph to be distancepreserving. We show that all hypercubes and graphs with delta(G)>=2n/31 are distancepreserving. Towards this end...
Show moreLet G be a simple graph on n vertices, where d_G(u,v) denotes the distance between vertices u and v in G. An induced subgraph H of G is isometric if d_H(u,v)=d_G(u,v) for all u,v in V(H). We say that G is a distancepreserving graph if G contains at least one isometric subgraph of order k for every k where 1<=k<=n.A number of sufficient conditions exist for a graph to be distancepreserving. We show that all hypercubes and graphs with delta(G)>=2n/31 are distancepreserving. Towards this end, we carefully examine the role of "forbidden" subgraphs. We discuss our observations, and provide some conjectures which we computationally verified for small values of n. We say that a distancepreserving graph is sequentially distancepreserving if each subgraph in the set of isometric subgraphs is a superset of the previous one, and consider this special case as well.There are a number of questions involving the construction of distancepreserving graphs. We show that it is always possible to add an edge to a noncomplete sequentially distancepreserving graph such that the augmented graph is still sequentially distancepreserving. We further conjecture that the same is true of all distancepreserving graphs. We discuss our observations on making nondistancepreserving graphs into distance preserving ones via adding edges. We show methods for constructing regular distancepreserving graphs, and consider constructing distancepreserving graphs for arbitrary degree sequences. As before, all conjectures here have been computationally verified for small values of n.
Show less
 Title
 Edge impact in graphs and social network matrix completion
 Creator
 Ross, Dennis
 Date
 2016
 Collection
 Electronic Theses & Dissertations
 Description

Every graph G can be associated with many wellknown invariant properties along with their corresponding values. A framework is proposed to measure the change in any particular invariant upon addition of a new edge $e$ in the resulting graph G+e. In graphs, the Pimpact of an edge e is the `magnitude' of the difference between the values of the invariant P in graphs G+e from G. Several famous invariants are explored and a proof towards optimal edge addition for distanceimpact in trees is...
Show moreEvery graph G can be associated with many wellknown invariant properties along with their corresponding values. A framework is proposed to measure the change in any particular invariant upon addition of a new edge $e$ in the resulting graph G+e. In graphs, the Pimpact of an edge e is the `magnitude' of the difference between the values of the invariant P in graphs G+e from G. Several famous invariants are explored and a proof towards optimal edge addition for distanceimpact in trees is given. A natural application to measuring the impact of edge addition to a graph is that of link prediction. An efficient algorithm for link prediction even with coldstart vertices using a subspace sharing method that decouples matrix completion and side information transduction is presented. This method is extended to predict ratings in useritem recommender systems where both may be coldstart.
Show less