Graphs admitting (1, ≤ 2)-identifying codes
dc.contributor.author | Lang, Julie | en_US |
dc.date.accessioned | 2014-08-18T14:03:40Z | |
dc.date.available | 2014-08-18T14:03:40Z | |
dc.date.graduationmonth | August | en_US |
dc.date.issued | 2014-08-18 | |
dc.date.published | 2014 | en_US |
dc.description.abstract | 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. | en_US |
dc.description.advisor | Sarah Reznikoff | en_US |
dc.description.degree | Master of Science | en_US |
dc.description.department | Department of Mathematics | en_US |
dc.description.level | Masters | en_US |
dc.identifier.uri | http://hdl.handle.net/2097/18260 | |
dc.language.iso | en_US | en_US |
dc.publisher | Kansas State University | en |
dc.subject | Identifying codes | en_US |
dc.subject | Graph theory | en_US |
dc.subject | Dominating sets | en_US |
dc.subject.umi | Mathematics (0405) | en_US |
dc.title | Graphs admitting (1, ≤ 2)-identifying codes | en_US |
dc.type | Thesis | en_US |