Investigations into the ranks of regular graphs

**Authors:**Garner, Charles R.**Date:**2012-08-17**Subjects:**Graph theory , Graphic methods , Spectral theory (Mathematics) , Eigenvalues**Type:**Thesis**Identifier:**uj:2622 , http://hdl.handle.net/10210/6069**Description:**Ph.D. , In this thesis, the ranks of many types of regular and strongly regular graphs are determined. Also determined are ranks of regular graphs under unary operations: the line graph, the complement, the subdivision graph, the connected cycle, the complete subdivision graph, and the total graph. The binary operations considered are the Cartesian product and the complete product. The ranks of the Cartesian product of regular graphs have been investigated previously in [BBD1]; here, we summarise and extend those results to include more regular graphs. We also examine a special nonregular graph, the path. Ranks of paths and products of graphs involving paths are presented as well**Full Text:**

**Authors:**Garner, Charles R.**Date:**2012-08-17**Subjects:**Graph theory , Graphic methods , Spectral theory (Mathematics) , Eigenvalues**Type:**Thesis**Identifier:**uj:2622 , http://hdl.handle.net/10210/6069**Description:**Ph.D. , In this thesis, the ranks of many types of regular and strongly regular graphs are determined. Also determined are ranks of regular graphs under unary operations: the line graph, the complement, the subdivision graph, the connected cycle, the complete subdivision graph, and the total graph. The binary operations considered are the Cartesian product and the complete product. The ranks of the Cartesian product of regular graphs have been investigated previously in [BBD1]; here, we summarise and extend those results to include more regular graphs. We also examine a special nonregular graph, the path. Ranks of paths and products of graphs involving paths are presented as well**Full Text:**

Generalized chromatic numbers and invariants of hereditary graph properties

**Authors:**Dorfling, Samantha**Date:**2011-12-06**Subjects:**Invariants , Graphic methods , Graph theory**Type:**Thesis**Identifier:**uj:1784 , http://hdl.handle.net/10210/4149**Description:**D. Phil (Mathematics) , In this thesis we investigate generalized chromatic numbers in the context of hereditary graph properties. We also investigate the general topic of invariants of graphs as well as graph properties. In Chapter 1 we give relevant definitions and terminology pertaining to graph properties. In Chapter 2 we investigate generalized chromatic numbers of some well-known additive hereditary graph properties. This problem necessitates the investigation of reducible bounds. One of the results here is an improvement on a known upper bound for the path partition number of the property Wk. We also look at the generalized chromatic number of infinite graphs and hereby establish the connection between the generalized chromatic number of properties and infinite graphs. In Chapter 3 the analogous question of the generalized edge-chromatic number of some well-known additive hereditary properties is investigated. Similarly we find decomposable bounds and are also able to find generalized edge-chromatic numbers of properties using some well-known decomposable bounds. In Chapter 4 we investigate the more general topic of graph invariants and the role they play in chains of graph properties and then conversely the invariants that arise from chains of graph properties. Moreover we investigate the effects on monotonicity of the invariants versus heredity and additivity of graph properties. In Chapter 5 the general topic of invariants of graph properties defined in terms of the set of minimal forbidden subgraphs of the properties is studied. This enables us to investigate invariants so defined on binary operations between graph properties. In Chapter 6 the notion of natural and near-natural invariants are introduced and are also studied on binary operations of graph properties. The set of minimal forbidden subgraphs again plays a role in the definition of invariants here and this then leads us to study the completion number of a property.**Full Text:**

**Authors:**Dorfling, Samantha**Date:**2011-12-06**Subjects:**Invariants , Graphic methods , Graph theory**Type:**Thesis**Identifier:**uj:1784 , http://hdl.handle.net/10210/4149**Description:**D. Phil (Mathematics) , In this thesis we investigate generalized chromatic numbers in the context of hereditary graph properties. We also investigate the general topic of invariants of graphs as well as graph properties. In Chapter 1 we give relevant definitions and terminology pertaining to graph properties. In Chapter 2 we investigate generalized chromatic numbers of some well-known additive hereditary graph properties. This problem necessitates the investigation of reducible bounds. One of the results here is an improvement on a known upper bound for the path partition number of the property Wk. We also look at the generalized chromatic number of infinite graphs and hereby establish the connection between the generalized chromatic number of properties and infinite graphs. In Chapter 3 the analogous question of the generalized edge-chromatic number of some well-known additive hereditary properties is investigated. Similarly we find decomposable bounds and are also able to find generalized edge-chromatic numbers of properties using some well-known decomposable bounds. In Chapter 4 we investigate the more general topic of graph invariants and the role they play in chains of graph properties and then conversely the invariants that arise from chains of graph properties. Moreover we investigate the effects on monotonicity of the invariants versus heredity and additivity of graph properties. In Chapter 5 the general topic of invariants of graph properties defined in terms of the set of minimal forbidden subgraphs of the properties is studied. This enables us to investigate invariants so defined on binary operations between graph properties. In Chapter 6 the notion of natural and near-natural invariants are introduced and are also studied on binary operations of graph properties. The set of minimal forbidden subgraphs again plays a role in the definition of invariants here and this then leads us to study the completion number of a property.**Full Text:**

- «
- ‹
- 1
- ›
- »