On the square of an oriented graph conjecture

College

College of Science

Department/Unit

Mathematics and Statistics Department

Document Type

Conference Proceeding

Source Title

DLSU Research Congress 2016

Publication Date

3-2016

Abstract

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

html

Disciplines

Mathematics

Keywords

Graph theory; Directed graphs

Upload File

wf_no

This document is currently not available here.

Share

COinS