On the square of an oriented graph conjecture
In 1993, Paul Seymour posed the problem that for every oriented graph G there exist a vertex whose out-degree at least doubles when you square the oriented graph; that is, if G = (V (G), A(G)) and denote δ+G (x) to be the out-degree of vertex x in the graph G, then there exists x ∈ (G) such that δ+(...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | text |
| Published: |
Animo Repository
2016
|
| Subjects: | |
| Online Access: | https://animorepository.dlsu.edu.ph/faculty_research/13458 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | De La Salle University |
| Summary: | In 1993, Paul Seymour posed the problem that for every oriented graph G there exist a vertex whose out-degree at least doubles when you square the oriented graph; that is, if G = (V (G), A(G)) and denote δ+G (x) to be the out-degree of vertex x in the graph G, then there exists x ∈ (G) such that δ+(G2)(x) ≥ 2δ+G (x). This problem is also listed in the open problems in the webpage of the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS -http://dimacs.rutgers.edu/ hochberg/undopen /graphtheory /graphtheory.html).We verify this conjecture for some families of graphs namely paths, cycles and star graphs. Moreover, we identify which of the vertices in the graph satisfies the assertion in the conjecture for most cases of the orientations of path, cycle and star graphs.The general idea is to identify the possible orientations of the said families of graphs and from those feasible orientations analyse the neighbourhoods of each vertex. We also relate the second neighbourhood conjecture to the square of an oriented graph conjecture, that is, if the second neighbourhood conjecture is true then it must be the case that the square of an oriented graph conjecture must be true |
|---|