Master of Science / Department of Mathematics / Sarah Reznikoff / A (1, ≤ 2)-identifying code is a subset of the vertex set C of a graph such that each
pair of vertices intersects C in a distinct way. This has useful applications in locating
errors in multiprocessor networks and threat monitoring. At the time of writing, there
is no simply-stated rule that will indicate if a graph is (1, ≤ 2)-identifiable. As such, we
discuss properties that must be satisfied by a valid (1, ≤ 2)-identifying code, characteristics of a graph which preclude the existence of a (1, ≤ 2)-identifying code, and relationships between the maximum degree and order of (1, ≤ 2)-identifiable graphs. Additionally, we show that (1, ≤ 2)-identifiable graphs have no forbidden induced subgraphs and provide a list of (1, ≤ 2)-identifiable graphs with minimum (1, ≤ 2)-identifying codes indicated.
Identifer | oai:union.ndltd.org:KSU/oai:krex.k-state.edu:2097/18260 |
Date | January 1900 |
Creators | Lang, Julie |
Publisher | Kansas State University |
Source Sets | K-State Research Exchange |
Language | en_US |
Detected Language | English |
Type | Thesis |
Page generated in 0.0015 seconds