Structural properties of twin-free graphs
Summary: Consider a connected undirected graph \(G=(V,E)\), a set \(C \subseteq V\), and an integer \(r\geq 1\). For any vertex \(v\) in \(V\), let \(B_r(v)\) denote the ball of radius \(r\) centered at \(v\), i.e., the set of all vertices linked to \(v\) by a path of at most \(r\) edges. If for all vertices \(v \in V\), the sets \(B_r(v) \cap C\) are all nonempty and different, then we call \(C\) an \(r\)-identifying code. A graph admits at least one \(r\)-identifying code if and only if it is \(r\)-twin-free, that is, the sets \(B_r(v)\), \(v \in V\), are all different. We study some structural problems in \(r\)-twin-free graphs, such as the existence of the path with \(2r+1\) vertices as a subgraph, or the consequences of deleting one vertex.
- Induced paths in twin-free graphs
- On the number of optimal identifying codes in a twin-free graph
- Extremal values for identification, domination and maximum cliques in twin-free graphs.
- Minimum sizes of identifying codes in graphs differing by one vertex
- Minimum sizes of identifying codes in graphs differing by one edge
- Induced paths in twin-free graphs
- On \(r\)-locating-dominating sets in paths
- On the size of identifying codes in binary hypercubes
- Twin subgraphs and core-semiperiphery-periphery structures
- Minimum sizes of identifying codes in graphs differing by one edge
- Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs
- Minimum sizes of identifying codes in graphs differing by one vertex
- On cages admitting identifying codes
- Extremal graphs for the identifying code problem
- Twins in graphs
- On the ensemble of optimal identifying codes in a twin-free graph
- Extremal values for the maximum degree in a twin-free graph.
- Extremal values for identification, domination and maximum cliques in twin-free graphs.
- The difference between the metric dimension and the determining number of a graph
- Locating-domination and identification
- Identifying path covers in graphs
- On the size of identifying codes in triangle-free graphs
- On the number of optimal identifying codes in a twin-free graph
- Characterization theorems for the spaces of derivations of evolution algebras associated to graphs
- Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
- Some classifications of graphs with respect to a set adjacency relation
- On Iiro Honkala's contributions to identifying codes
- The minimum number of maximal independent sets in twin-free graphs
- A characterization of semitwin digraphs
This page was built for publication: Structural properties of twin-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870075)
