On detour homogeneous digraphs (Q1045177): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 23:56, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On detour homogeneous digraphs |
scientific article |
Statements
On detour homogeneous digraphs (English)
0 references
15 December 2009
0 references
Let \(D\) denote an \(m\)-(arc) coloured digraph with no loops and suppose the vertices that dominate some vertex \(v\) of \(D\) are partitioned into \(n\) subsets. Let \(D^-\) denote the \(m\)-coloured digraph obtained by \(D\) by replacing vertex \(v\) by \(n\) new vertices \(u_1,\dots, u_n\) and then replacing each arc \(vz\) or \(zv\) of colour \(j\) by \(n\) arcs of the form \(u_iz\) or \(zu_i\), for \(i=1,\dots,n\), of the same colour; \(D^-\) is said to be obtained from \(D\) by an in-state splitting. For any subset \(S\) of the vertices of \(D\), let \(S^-\) differ from \(S\) only in that if \(v\in S\), then \(v\) is replaced by \(u_1,\dots, u_n\) in \(S^-\). The authors prove, among other things, various results of the following form: If the subset \(S\) has a certain property \(P\) in \(D\) subject, perhaps, to certain conditions, then the subset \(S^-\) has the property \(P\) in \(D^-\). The properties \(P\) considered are all defined in terms of monochromatic paths.
0 references
digraph
0 references
oriented graph
0 references
detour homogeneous
0 references
homogeneously traceable
0 references
traceable
0 references