Graphs admitting (1, ≤ 2)-identifying codes

Date

2014-08-18

Journal Title

Journal ISSN

Volume Title

Publisher

Kansas State University

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.

Description

Keywords

Identifying codes, Graph theory, Dominating sets

Graduation Month

August

Degree

Master of Science

Department

Department of Mathematics

Major Professor

Sarah Reznikoff

Date

2014

Type

Thesis

Citation