Neighborhood conditions for balanced independent sets in bipartite graphs (Q1381845): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q5615282 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A generalization of Ore's Theorem involving neighborhood unions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Neighbourhood unions and Hamiltonian properties in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Neighborhood unions and hamilton cycles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Hamiltonian bipartite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cycles and Connectivity in Graphs / rank | |||
Normal rank |
Latest revision as of 11:55, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Neighborhood conditions for balanced independent sets in bipartite graphs |
scientific article |
Statements
Neighborhood conditions for balanced independent sets in bipartite graphs (English)
0 references
22 June 1998
0 references
Let us assume that \(\Gamma\) is a balanced bipartite graph (i.e., \(\Gamma\) admits a bipartition into two independent vertex sets with the same cardinality) of order \(2n\) in which all valences are \(\geq3\). We assume further that the neighborhood \(N(S)\) of any independent 4-subset \(S\) of \(V(\Gamma)\) consisting of two vertices from each side of the bipartition satisfies \(|N(S)|>n\). In this clearly-written, well-motivated, example-rich paper, the following conclusions are deduced: \(\Gamma\) is either Hamiltonian or contains a spanning subgraph consisting of a cycle and an isolated edge; \(\Gamma\) is traceable; \(\Gamma\) either has a 2-factor or belongs to a small subclass of examples in which \(n=7\). It is conjectured that under the above assumptions, \(\Gamma\) is Hamiltonian or belongs to this small subclass. By sharpening the inequality to \(|N(S)|>n+2\), the authors show that \(\Gamma\) is in fact Hamiltonian.
0 references
Hamiltonian
0 references
neighborhood union
0 references
bipartite graph
0 references
independent set
0 references
traceable
0 references
perfect matching
0 references