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.0018 seconds