Loop and cyclic niche graphs (Q1805299)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 753992
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Loop and cyclic niche graphs |
scientific article; zbMATH DE number 753992 |
Statements
Loop and cyclic niche graphs (English)
0 references
18 December 1995
0 references
The niche graph of a digraph \(D\) is the graph \(G\) such that an edge \((x, y)\) is in \(G\) if and only if there is a node \(z\) in \(D\) so that either \((x, z)\) and \((y, z)\) or \((z, x)\) and \((z, y)\) are arcs of \(D\). The problem of which graphs were the niche graph of acyclic digraphs have received much attention. The paper considers the effect of relaxing the requirement that the digraph be acyclic. Several new classes of graphs are found to be niche graphs, but many graphs still are neither niche graphs, nor can they be made into niche graphs by adding isolated nodes.
0 references
loop
0 references
cycle
0 references
niche graph
0 references
digraph
0 references
acyclic digraphs
0 references
0.894199788570404
0 references
