Graph orientations with edge-connection and parity constraints (Q1603262): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s004930200003 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1984188921 / rank | |||
Normal rank |
Latest revision as of 20:41, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graph orientations with edge-connection and parity constraints |
scientific article |
Statements
Graph orientations with edge-connection and parity constraints (English)
0 references
25 June 2002
0 references
For a graph \(G=(V,E)\), we say \(T\subseteq V\) is \(G\)-even if \(|T|+|E|\) is even. An orientation of \(G\) is \(T\)-odd if the in-degree of a node \(v\) is odd precisely when \(v\in T\). The main result of this paper is an NP and co-NP characterization of graphs admitting the property `\(G\) has an \(l\)-edge-connected \(T\)-odd orientation for every \(G\)-even subset \(T\) of nodes'. As a corollary it is also shown that every \(4\)-edge-connected graph \(G=(V,E)\) with a \(G\)-even subset \(T\) has a strongly connected \(T\)-odd orientation. Several related results combining parity and connectivity requirements are imposed.
0 references
connectivity
0 references
orientation
0 references