subject:(DIRECTED GRAPHS GRAPH THEORY )

1. Christopher, Jeffrey. Induced path number for the complementary prism of a grid graph.

Degree: 2019, University of Tennessee – Chattanooga

► The induced path number rho(G) of a graph G is defined as the minimum number of subsets into which the vertex set of G can… (more)

Subjects/Keywords: Graph theory; Directed graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Christopher, J. (2019). Induced path number for the complementary prism of a grid graph. (Masters Thesis). University of Tennessee – Chattanooga. Retrieved from https://scholar.utc.edu/theses/594

Chicago Manual of Style (16^th Edition):

Christopher, Jeffrey. “Induced path number for the complementary prism of a grid graph.” 2019. Masters Thesis, University of Tennessee – Chattanooga. Accessed December 09, 2019. https://scholar.utc.edu/theses/594.

MLA Handbook (7^th Edition):

Christopher, Jeffrey. “Induced path number for the complementary prism of a grid graph.” 2019. Web. 09 Dec 2019.

Vancouver:

Christopher J. Induced path number for the complementary prism of a grid graph. [Internet] [Masters thesis]. University of Tennessee – Chattanooga; 2019. [cited 2019 Dec 09]. Available from: https://scholar.utc.edu/theses/594.

Council of Science Editors:

Christopher J. Induced path number for the complementary prism of a grid graph. [Masters Thesis]. University of Tennessee – Chattanooga; 2019. Available from: https://scholar.utc.edu/theses/594

Hong Kong University of Science and Technology

2. Wang, Wenjie. Arc ideals and Cohen-Macaulay digraphs.

Degree: 2009, Hong Kong University of Science and Technology

URL: https://doi.org/10.14711/thesis-b1070096 ; http://repository.ust.hk/ir/bitstream/1783.1-7530/1/th_redirect.html

► In this thesis I introduce the concepts of arc ideals, unmixed digraphs, and Cohen-Macaulay digraphs, and study their algebraic and combinatorial properties by using commutative… (more)

Subjects/Keywords: Graph theory; Directed graphs; Cohen-Macaulay rings

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Wang, W. (2009). Arc ideals and Cohen-Macaulay digraphs. (Thesis). Hong Kong University of Science and Technology. Retrieved from https://doi.org/10.14711/thesis-b1070096 ; http://repository.ust.hk/ir/bitstream/1783.1-7530/1/th_redirect.html

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Wang, Wenjie. “Arc ideals and Cohen-Macaulay digraphs.” 2009. Thesis, Hong Kong University of Science and Technology. Accessed December 09, 2019. https://doi.org/10.14711/thesis-b1070096 ; http://repository.ust.hk/ir/bitstream/1783.1-7530/1/th_redirect.html.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Wang, Wenjie. “Arc ideals and Cohen-Macaulay digraphs.” 2009. Web. 09 Dec 2019.

Vancouver:

Wang W. Arc ideals and Cohen-Macaulay digraphs. [Internet] [Thesis]. Hong Kong University of Science and Technology; 2009. [cited 2019 Dec 09]. Available from: https://doi.org/10.14711/thesis-b1070096 ; http://repository.ust.hk/ir/bitstream/1783.1-7530/1/th_redirect.html.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Wang W. Arc ideals and Cohen-Macaulay digraphs. [Thesis]. Hong Kong University of Science and Technology; 2009. Available from: https://doi.org/10.14711/thesis-b1070096 ; http://repository.ust.hk/ir/bitstream/1783.1-7530/1/th_redirect.html

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Lethbridge

3. University of Lethbridge. Faculty of Arts and Science. Energy of graphs and digraphs .

Degree: 2010, University of Lethbridge

URL: http://hdl.handle.net/10133/2489

► The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. The concept is related to the… (more)

Subjects/Keywords: Graph theory; Directed graphs; Eigenvalues; Dissertations, Academic

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Science, U. o. L. F. o. A. a. (2010). Energy of graphs and digraphs . (Thesis). University of Lethbridge. Retrieved from http://hdl.handle.net/10133/2489

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Science, University of Lethbridge. Faculty of Arts and. “Energy of graphs and digraphs .” 2010. Thesis, University of Lethbridge. Accessed December 09, 2019. http://hdl.handle.net/10133/2489.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Science, University of Lethbridge. Faculty of Arts and. “Energy of graphs and digraphs .” 2010. Web. 09 Dec 2019.

Vancouver:

Science UoLFoAa. Energy of graphs and digraphs . [Internet] [Thesis]. University of Lethbridge; 2010. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10133/2489.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Science UoLFoAa. Energy of graphs and digraphs . [Thesis]. University of Lethbridge; 2010. Available from: http://hdl.handle.net/10133/2489

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Simon Fraser University

4. Bauslaugh, Bruce Lloyd. Homomorphisms of infinite directed graphs.

Degree: 1994, Simon Fraser University

URL: http://summit.sfu.ca/item/6543

Subjects/Keywords: Directed graphs.; Homomorphisms (Mathematics); Graph theory.

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Bauslaugh, B. L. (1994). Homomorphisms of infinite directed graphs. (Thesis). Simon Fraser University. Retrieved from http://summit.sfu.ca/item/6543

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Bauslaugh, Bruce Lloyd. “Homomorphisms of infinite directed graphs.” 1994. Thesis, Simon Fraser University. Accessed December 09, 2019. http://summit.sfu.ca/item/6543.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Bauslaugh, Bruce Lloyd. “Homomorphisms of infinite directed graphs.” 1994. Web. 09 Dec 2019.

Vancouver:

Bauslaugh BL. Homomorphisms of infinite directed graphs. [Internet] [Thesis]. Simon Fraser University; 1994. [cited 2019 Dec 09]. Available from: http://summit.sfu.ca/item/6543.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Bauslaugh BL. Homomorphisms of infinite directed graphs. [Thesis]. Simon Fraser University; 1994. Available from: http://summit.sfu.ca/item/6543

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of South Africa

5. Van der Linde, Jan Johannes. Enlarging directed graphs to ensure all nodes are contained.

Degree: 2015, University of South Africa

URL: http://hdl.handle.net/10500/21520

► Graph augmentation concerns the addition of edges to a graph to satisfy some connectivity property of a graph. Previous research in this field has been… (more)

Subjects/Keywords: Directed graphs; Graph enlargement; Cycle picking

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Van der Linde, J. J. (2015). Enlarging directed graphs to ensure all nodes are contained. (Masters Thesis). University of South Africa. Retrieved from http://hdl.handle.net/10500/21520

Chicago Manual of Style (16^th Edition):

Van der Linde, Jan Johannes. “Enlarging directed graphs to ensure all nodes are contained.” 2015. Masters Thesis, University of South Africa. Accessed December 09, 2019. http://hdl.handle.net/10500/21520.

MLA Handbook (7^th Edition):

Van der Linde, Jan Johannes. “Enlarging directed graphs to ensure all nodes are contained.” 2015. Web. 09 Dec 2019.

Vancouver:

Van der Linde JJ. Enlarging directed graphs to ensure all nodes are contained. [Internet] [Masters thesis]. University of South Africa; 2015. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10500/21520.

Council of Science Editors:

Van der Linde JJ. Enlarging directed graphs to ensure all nodes are contained. [Masters Thesis]. University of South Africa; 2015. Available from: http://hdl.handle.net/10500/21520

University of Victoria

6. Young, Kailyn M. 2-dipath and proper 2-dipath k-colourings: Two-dipath and proper two-dipath k-colourings.

Degree: Dept. of Mathematics and Statistics, 2011, University of Victoria

URL: http://hdl.handle.net/1828/3277

► A 2-dipath k-colouring of an oriented graph G is an assignment of k colours, 1,2, . . . , k, to the vertices of G… (more)

Subjects/Keywords: graph theory; oriented graphs; tournaments

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Young, K. M. (2011). 2-dipath and proper 2-dipath k-colourings: Two-dipath and proper two-dipath k-colourings. (Masters Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/3277

Chicago Manual of Style (16^th Edition):

Young, Kailyn M. “2-dipath and proper 2-dipath k-colourings: Two-dipath and proper two-dipath k-colourings.” 2011. Masters Thesis, University of Victoria. Accessed December 09, 2019. http://hdl.handle.net/1828/3277.

MLA Handbook (7^th Edition):

Young, Kailyn M. “2-dipath and proper 2-dipath k-colourings: Two-dipath and proper two-dipath k-colourings.” 2011. Web. 09 Dec 2019.

Vancouver:

Young KM. 2-dipath and proper 2-dipath k-colourings: Two-dipath and proper two-dipath k-colourings. [Internet] [Masters thesis]. University of Victoria; 2011. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/1828/3277.

Council of Science Editors:

Young KM. 2-dipath and proper 2-dipath k-colourings: Two-dipath and proper two-dipath k-colourings. [Masters Thesis]. University of Victoria; 2011. Available from: http://hdl.handle.net/1828/3277

University of Newcastle

7. Marshall, Kim. Extremal networks and connectivity.

Degree: PhD, 2011, University of Newcastle

URL: http://hdl.handle.net/1959.13/927974

►

Research Doctorate - Doctor of Philosophy (PhD)

In this thesis we consider questions in two separate but related research areas in the field of graph… (more)

Subjects/Keywords: extremal graphs; connectivity; graph theory

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Marshall, K. (2011). Extremal networks and connectivity. (Doctoral Dissertation). University of Newcastle. Retrieved from http://hdl.handle.net/1959.13/927974

Chicago Manual of Style (16^th Edition):

Marshall, Kim. “Extremal networks and connectivity.” 2011. Doctoral Dissertation, University of Newcastle. Accessed December 09, 2019. http://hdl.handle.net/1959.13/927974.

MLA Handbook (7^th Edition):

Marshall, Kim. “Extremal networks and connectivity.” 2011. Web. 09 Dec 2019.

Vancouver:

Marshall K. Extremal networks and connectivity. [Internet] [Doctoral dissertation]. University of Newcastle; 2011. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/1959.13/927974.

Council of Science Editors:

Marshall K. Extremal networks and connectivity. [Doctoral Dissertation]. University of Newcastle; 2011. Available from: http://hdl.handle.net/1959.13/927974

8. Plaisted, Daniel. On a graph parameter related to vertex labelings and its application to minimum rank problems in graph theory.

Degree: 2019, University of Tennessee – Chattanooga

URL: https://scholar.utc.edu/theses/611

► This thesis regards the minimum rank and minimum positive semidefinite rank of a simple graph. A graph parameter, called the minimum labeling degree (mld), is… (more)

Subjects/Keywords: Graph theory; Representations of graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Plaisted, D. (2019). On a graph parameter related to vertex labelings and its application to minimum rank problems in graph theory. (Masters Thesis). University of Tennessee – Chattanooga. Retrieved from https://scholar.utc.edu/theses/611

Chicago Manual of Style (16^th Edition):

Plaisted, Daniel. “On a graph parameter related to vertex labelings and its application to minimum rank problems in graph theory.” 2019. Masters Thesis, University of Tennessee – Chattanooga. Accessed December 09, 2019. https://scholar.utc.edu/theses/611.

MLA Handbook (7^th Edition):

Plaisted, Daniel. “On a graph parameter related to vertex labelings and its application to minimum rank problems in graph theory.” 2019. Web. 09 Dec 2019.

Vancouver:

Plaisted D. On a graph parameter related to vertex labelings and its application to minimum rank problems in graph theory. [Internet] [Masters thesis]. University of Tennessee – Chattanooga; 2019. [cited 2019 Dec 09]. Available from: https://scholar.utc.edu/theses/611.

Council of Science Editors:

Plaisted D. On a graph parameter related to vertex labelings and its application to minimum rank problems in graph theory. [Masters Thesis]. University of Tennessee – Chattanooga; 2019. Available from: https://scholar.utc.edu/theses/611

9. Gutierrez Alva, Juan Gabriel. O problema do multicorte dirigido mínimo.

Degree: Mestrado, Ciência da Computação, 2012, University of São Paulo

URL: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22012013-160000/ ;

►

O Problema do Multicorte Dirigido Mínimo é um problema clássico em otimização combinatória. Ele é NP-difícil mesmo para instâncias muito simples. Este trabalho faz uma… (more)

Subjects/Keywords: algorithms in graphs; algoritmos em grafos; directed multicut; graph theory; multicommodity disconnecting set.; multicommodity disconnecting set.; multicorte dirigido; teoria dos grafos

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Gutierrez Alva, J. G. (2012). O problema do multicorte dirigido mínimo. (Masters Thesis). University of São Paulo. Retrieved from http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22012013-160000/ ;

Chicago Manual of Style (16^th Edition):

Gutierrez Alva, Juan Gabriel. “O problema do multicorte dirigido mínimo.” 2012. Masters Thesis, University of São Paulo. Accessed December 09, 2019. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22012013-160000/ ;.

MLA Handbook (7^th Edition):

Gutierrez Alva, Juan Gabriel. “O problema do multicorte dirigido mínimo.” 2012. Web. 09 Dec 2019.

Vancouver:

Gutierrez Alva JG. O problema do multicorte dirigido mínimo. [Internet] [Masters thesis]. University of São Paulo; 2012. [cited 2019 Dec 09]. Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22012013-160000/ ;.

Council of Science Editors:

Gutierrez Alva JG. O problema do multicorte dirigido mínimo. [Masters Thesis]. University of São Paulo; 2012. Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22012013-160000/ ;

10. Uematsu, Naoya. Lights out game with cellular automation.

Degree: 2016, University of Northern Iowa

URL: https://scholarworks.uni.edu/etd/234

1 PDF file (x, 53 pages) Advisors/Committee Members: Douglas J. Shaw, Chair.

Subjects/Keywords: Directed graphs; Graph theory; Combinatorial geometry; Lights out (Game)

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Uematsu, N. (2016). Lights out game with cellular automation. (Thesis). University of Northern Iowa. Retrieved from https://scholarworks.uni.edu/etd/234

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Uematsu, Naoya. “Lights out game with cellular automation.” 2016. Thesis, University of Northern Iowa. Accessed December 09, 2019. https://scholarworks.uni.edu/etd/234.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Uematsu, Naoya. “Lights out game with cellular automation.” 2016. Web. 09 Dec 2019.

Vancouver:

Uematsu N. Lights out game with cellular automation. [Internet] [Thesis]. University of Northern Iowa; 2016. [cited 2019 Dec 09]. Available from: https://scholarworks.uni.edu/etd/234.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Uematsu N. Lights out game with cellular automation. [Thesis]. University of Northern Iowa; 2016. Available from: https://scholarworks.uni.edu/etd/234

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Kansas State University

11. Chowdhury, Zahirul Kabir. The representation of data base relations through digraphs.

Degree: 1984, Kansas State University

URL: http://hdl.handle.net/2097/9722

Subjects/Keywords: Directed graphs; Graph theory; Database management – Computer programs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Chowdhury, Z. K. (1984). The representation of data base relations through digraphs. (Thesis). Kansas State University. Retrieved from http://hdl.handle.net/2097/9722

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Chowdhury, Zahirul Kabir. “The representation of data base relations through digraphs.” 1984. Thesis, Kansas State University. Accessed December 09, 2019. http://hdl.handle.net/2097/9722.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Chowdhury, Zahirul Kabir. “The representation of data base relations through digraphs.” 1984. Web. 09 Dec 2019.

Vancouver:

Chowdhury ZK. The representation of data base relations through digraphs. [Internet] [Thesis]. Kansas State University; 1984. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/2097/9722.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Chowdhury ZK. The representation of data base relations through digraphs. [Thesis]. Kansas State University; 1984. Available from: http://hdl.handle.net/2097/9722

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

12. Molla, Theodore. On Tiling Directed Graphs with Cycles and Tournaments.

Degree: PhD, Mathematics, 2013, Arizona State University

URL: http://repository.asu.edu/items/18715

► A tiling is a collection of vertex disjoint subgraphs called tiles. If the tiles are all isomorphic to a graph H then the tiling is… (more)

Subjects/Keywords: Mathematics; Combinatorics; Directed Graphs; Graph Theory

…vertices. 14 1.5 Tiling directed graphs with cycles Call a graph r-regular if d(v)… …x29; : v ∈ V }. A tournament is a directed graph in which there is exactly one edge… …x29; ≥ n/2. We now consider this same type of problem when G and H are directed graphs. We… …m) to be the directed graph formed from GI (n, m) by replacing all edges… …x28;D) ≥ 2k k+1 − 2. We say a directed graph D is strongly d-connected if for any…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Molla, T. (2013). On Tiling Directed Graphs with Cycles and Tournaments. (Doctoral Dissertation). Arizona State University. Retrieved from http://repository.asu.edu/items/18715

Chicago Manual of Style (16^th Edition):

Molla, Theodore. “On Tiling Directed Graphs with Cycles and Tournaments.” 2013. Doctoral Dissertation, Arizona State University. Accessed December 09, 2019. http://repository.asu.edu/items/18715.

MLA Handbook (7^th Edition):

Molla, Theodore. “On Tiling Directed Graphs with Cycles and Tournaments.” 2013. Web. 09 Dec 2019.

Vancouver:

Molla T. On Tiling Directed Graphs with Cycles and Tournaments. [Internet] [Doctoral dissertation]. Arizona State University; 2013. [cited 2019 Dec 09]. Available from: http://repository.asu.edu/items/18715.

Council of Science Editors:

Molla T. On Tiling Directed Graphs with Cycles and Tournaments. [Doctoral Dissertation]. Arizona State University; 2013. Available from: http://repository.asu.edu/items/18715

Ryerson University

13. Patel, Sonal. Clique Listing Algorithms and Characteristics of Cliques in Random Graphics.

Degree: 2010, Ryerson University

URL: https://digital.library.ryerson.ca/islandora/object/RULA%3A1845

► In this thesis we address three main problems in clique detection in the area of Graph Theory. i) Most of current methods for clique detection… (more)

Subjects/Keywords: Random graphs; Graph theory; Algorithms; Graph algorithms

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Patel, S. (2010). Clique Listing Algorithms and Characteristics of Cliques in Random Graphics. (Thesis). Ryerson University. Retrieved from https://digital.library.ryerson.ca/islandora/object/RULA%3A1845

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Patel, Sonal. “Clique Listing Algorithms and Characteristics of Cliques in Random Graphics.” 2010. Thesis, Ryerson University. Accessed December 09, 2019. https://digital.library.ryerson.ca/islandora/object/RULA%3A1845.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Patel, Sonal. “Clique Listing Algorithms and Characteristics of Cliques in Random Graphics.” 2010. Web. 09 Dec 2019.

Vancouver:

Patel S. Clique Listing Algorithms and Characteristics of Cliques in Random Graphics. [Internet] [Thesis]. Ryerson University; 2010. [cited 2019 Dec 09]. Available from: https://digital.library.ryerson.ca/islandora/object/RULA%3A1845.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Patel S. Clique Listing Algorithms and Characteristics of Cliques in Random Graphics. [Thesis]. Ryerson University; 2010. Available from: https://digital.library.ryerson.ca/islandora/object/RULA%3A1845

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

14. Granger, Valerie, 1985-. GIT-equivalence and semi-stable subcategories of quiver representations.

Degree: 2016, University of Missouri – Columbia

URL: http://hdl.handle.net/10355/56527

► The main investigation in this thesis is to determine when two weights give rise to the same semi-stable subcategory in the case of representations of… (more)

Subjects/Keywords: Directed graphs; Representations of graphs; Paths and cycles (Graph theory)

…quivers, which are simply directed graphs. Quivers and their representations occur most… …Notions for Quivers A quiver is a directed graph. That is, a quiver consists of Q = (Q0… …naturally in representation theory of finite dimensional algebras. They turn out to have an… …theory, the main objects of study are the so-called semi-stable representations. These are… …Mumford criterion in Geometric Invariant Theory. Semistable representations play a central role…

1 more image…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Granger, Valerie, 1. (2016). GIT-equivalence and semi-stable subcategories of quiver representations. (Thesis). University of Missouri – Columbia. Retrieved from http://hdl.handle.net/10355/56527

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Granger, Valerie, 1985-. “GIT-equivalence and semi-stable subcategories of quiver representations.” 2016. Thesis, University of Missouri – Columbia. Accessed December 09, 2019. http://hdl.handle.net/10355/56527.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Granger, Valerie, 1985-. “GIT-equivalence and semi-stable subcategories of quiver representations.” 2016. Web. 09 Dec 2019.

Vancouver:

Granger, Valerie 1. GIT-equivalence and semi-stable subcategories of quiver representations. [Internet] [Thesis]. University of Missouri – Columbia; 2016. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10355/56527.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Granger, Valerie 1. GIT-equivalence and semi-stable subcategories of quiver representations. [Thesis]. University of Missouri – Columbia; 2016. Available from: http://hdl.handle.net/10355/56527

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Indian Institute of Science

15. Rajendraprasad, Deepak. Rainbow Colouring and Some Dimensional Problems in Graph Theory.

Degree: 2013, Indian Institute of Science

URL: http://etd.iisc.ernet.in/2005/3336 ; http://etd.iisc.ernet.in/abstracts/4201/G25730-Abs.pdf

► This thesis touches three diﬀerent topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is… (more)

Subjects/Keywords: Graph Theory; Rainbow Coloring - Graphs; Product Dimension - Graphs; Boxicity; Cubicity; Hypergraphs; Product Graphs; Forests Graphs; Treewidth Graphs; Tree (Graph Theory); Split Graphs; Threshold Graphs; Graph - Coloring; Rainbow Connection; Computer Science

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Rajendraprasad, D. (2013). Rainbow Colouring and Some Dimensional Problems in Graph Theory. (Thesis). Indian Institute of Science. Retrieved from http://etd.iisc.ernet.in/2005/3336 ; http://etd.iisc.ernet.in/abstracts/4201/G25730-Abs.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Rajendraprasad, Deepak. “Rainbow Colouring and Some Dimensional Problems in Graph Theory.” 2013. Thesis, Indian Institute of Science. Accessed December 09, 2019. http://etd.iisc.ernet.in/2005/3336 ; http://etd.iisc.ernet.in/abstracts/4201/G25730-Abs.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Rajendraprasad, Deepak. “Rainbow Colouring and Some Dimensional Problems in Graph Theory.” 2013. Web. 09 Dec 2019.

Vancouver:

Rajendraprasad D. Rainbow Colouring and Some Dimensional Problems in Graph Theory. [Internet] [Thesis]. Indian Institute of Science; 2013. [cited 2019 Dec 09]. Available from: http://etd.iisc.ernet.in/2005/3336 ; http://etd.iisc.ernet.in/abstracts/4201/G25730-Abs.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Rajendraprasad D. Rainbow Colouring and Some Dimensional Problems in Graph Theory. [Thesis]. Indian Institute of Science; 2013. Available from: http://etd.iisc.ernet.in/2005/3336 ; http://etd.iisc.ernet.in/abstracts/4201/G25730-Abs.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Colorado

16. Fox, Alyson Lindsey. Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs.

Degree: PhD, Applied Mathematics, 2017, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/96

► Relational datasets are often modeled as an unsigned, undirected graph due the nice properties of the resulting graph Laplacian, but information is lost if… (more)

Subjects/Keywords: Algebraic Multigrid; Directed graphs; Graph Laplacians; Gremban's expansion; Signed graphs; Applied Mechanics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Fox, A. L. (2017). Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/96

Chicago Manual of Style (16^th Edition):

Fox, Alyson Lindsey. “Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs.” 2017. Doctoral Dissertation, University of Colorado. Accessed December 09, 2019. https://scholar.colorado.edu/appm_gradetds/96.

MLA Handbook (7^th Edition):

Fox, Alyson Lindsey. “Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs.” 2017. Web. 09 Dec 2019.

Vancouver:

Fox AL. Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs. [Internet] [Doctoral dissertation]. University of Colorado; 2017. [cited 2019 Dec 09]. Available from: https://scholar.colorado.edu/appm_gradetds/96.

Council of Science Editors:

Fox AL. Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs. [Doctoral Dissertation]. University of Colorado; 2017. Available from: https://scholar.colorado.edu/appm_gradetds/96

University of Colorado

17. Fox, Alyson Lindsey. Algebraic Multigrid(AMG) for Graph Laplacian Linear Systems: Extensions of AMG for Signed, Undirected and Unsigned, Directed Graphs.

Degree: PhD, 2017, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/121

► Relational datasets are often modeled as an unsigned, undirected graph due the nice properties of the resulting graph Laplacian, but information is lost if… (more)

Subjects/Keywords: algebraic multigrid; directed graphs; graph laplacians; gremban's expansion; signed graphs; Algebra; Applied Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Fox, A. L. (2017). Algebraic Multigrid(AMG) for Graph Laplacian Linear Systems: Extensions of AMG for Signed, Undirected and Unsigned, Directed Graphs. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/121

Chicago Manual of Style (16^th Edition):

Fox, Alyson Lindsey. “Algebraic Multigrid(AMG) for Graph Laplacian Linear Systems: Extensions of AMG for Signed, Undirected and Unsigned, Directed Graphs.” 2017. Doctoral Dissertation, University of Colorado. Accessed December 09, 2019. https://scholar.colorado.edu/appm_gradetds/121.

MLA Handbook (7^th Edition):

Fox, Alyson Lindsey. “Algebraic Multigrid(AMG) for Graph Laplacian Linear Systems: Extensions of AMG for Signed, Undirected and Unsigned, Directed Graphs.” 2017. Web. 09 Dec 2019.

Vancouver:

Fox AL. Algebraic Multigrid(AMG) for Graph Laplacian Linear Systems: Extensions of AMG for Signed, Undirected and Unsigned, Directed Graphs. [Internet] [Doctoral dissertation]. University of Colorado; 2017. [cited 2019 Dec 09]. Available from: https://scholar.colorado.edu/appm_gradetds/121.

Council of Science Editors:

Fox AL. Algebraic Multigrid(AMG) for Graph Laplacian Linear Systems: Extensions of AMG for Signed, Undirected and Unsigned, Directed Graphs. [Doctoral Dissertation]. University of Colorado; 2017. Available from: https://scholar.colorado.edu/appm_gradetds/121

Virginia Tech

18. Misra, Supratik Kumar. Efficient Graph Techniques for Partial Scan Pattern Debug and Bounded Model Checkers.

Degree: MS, Electrical and Computer Engineering, 2012, Virginia Tech

URL: http://hdl.handle.net/10919/31153

► Continuous advances in VLSI technology have led to more complex digital designs and shrinking transistor sizes. Due to these developments, design verification and manufacturing test… (more)

▼ Continuous advances in VLSI technology have led to more complex digital designs and shrinking transistor sizes. Due to these developments, design verification and manufacturing test have gained more importance and 70 % of the design expenditure in on validation processes. Electronic Design Automation (EDA) tools play a huge role in the validation process with various verification and test tools. Their efficiency have a high impact in saving time and money in this competitive market. Direct Acyclic Graphs (DAGs) are the backbone for most of the EDA tools. DAG is the most efficient data structure to store circuit information and also have efficient backt traversing structure which help in developing reasoning/ debugging tools. In this thesis, we focus on two such EDA tools using graphs as their underlying structure for circuit information storage â ¢ Scan pattern Debugger for Partial Scan Designs â ¢ Circuit SAT Bounded Model Checkers We developed a complete Interactive Scan Pattern Debugger Suite currently being used in the industry for next generation microprocessor design. The back end is an implication graph based sequential logic simulator which creates a Debug Implication Graph during the logic simulation of the failing patterns. An efficient node traversal mechanism across time frames, in the DIG, is used to perform the root-cause analysis for the failing scan-cells. In addition, the debugger provides visibility into the circuit internals to understand and fix the root-cause. We integrated the proposed technique into the scan ATPG flow for industrial microprocessor designs. We were able to resolve the First Silicon logical pattern failures within hours, which would have otherwise taken a few days of manual effort for root-causing the failure, understanding the root-cause and fixing it. For our circuit SAT implementation, we replace the internal implication graph used by the SAT solver with our debug implication graph (DIG). There is a high amount of circuit unrolling in circuit SAT/ BMC (Bounded Model Checking) problems which creates copies of the same combinational blocks in multiple time frames. This allows us to use the repetitive circuit structure and club it with the CNF database in the SAT solver. We propose a new data structure to store data in a circuit SAT solver which results up to 90% reduction in number of nodes. Advisors/Committee Members: Hsiao, Michael S. (committeechair), Shukla, Sandeep K. (committee member), Abbott, A. Lynn (committee member).

Subjects/Keywords: Directed Acyclic Graph; Partial Scan Design; Pattern Debugger; Implication Graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Misra, S. K. (2012). Efficient Graph Techniques for Partial Scan Pattern Debug and Bounded Model Checkers. (Masters Thesis). Virginia Tech. Retrieved from http://hdl.handle.net/10919/31153

Chicago Manual of Style (16^th Edition):

Misra, Supratik Kumar. “Efficient Graph Techniques for Partial Scan Pattern Debug and Bounded Model Checkers.” 2012. Masters Thesis, Virginia Tech. Accessed December 09, 2019. http://hdl.handle.net/10919/31153.

MLA Handbook (7^th Edition):

Misra, Supratik Kumar. “Efficient Graph Techniques for Partial Scan Pattern Debug and Bounded Model Checkers.” 2012. Web. 09 Dec 2019.

Vancouver:

Misra SK. Efficient Graph Techniques for Partial Scan Pattern Debug and Bounded Model Checkers. [Internet] [Masters thesis]. Virginia Tech; 2012. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10919/31153.

Council of Science Editors:

Misra SK. Efficient Graph Techniques for Partial Scan Pattern Debug and Bounded Model Checkers. [Masters Thesis]. Virginia Tech; 2012. Available from: http://hdl.handle.net/10919/31153

University of Miami

19. Ellzey, Brittney. On Chromatic Quasisymmetric Functions of Directed Graphs.

Degree: PhD, Mathematics (Arts and Sciences), 2018, University of Miami

URL: https://scholarlyrepository.miami.edu/oa_dissertations/2091

► In 1912, Birkhoff introduced the chromatic polynomial of a graph, which counts the number of proper colorings of a graph. In 1995, Stanley introduced the… (more)

▼ In 1912, Birkhoff introduced the chromatic polynomial of a graph, which counts the number of proper colorings of a graph. In 1995, Stanley introduced the chromatic symmetric function of a graph, a symmetric function analog of the chromatic polynomial of a graph. The Stanley-Stembridge e-positivity conjecture is a longstanding conjecture that states that the chromatic symmetric function of a certain class of graphs has nonnegative coefficients when expanded in the elementary symmetric function basis. In 2012, Shareshian and Wachs introduced the chromatic quasisymmetric function of a labeled graph, a refinement of the chromatic symmetric function. Shareshian and Wachs described their own e-positivity conjecture for chromatic quasisymmetric functions which generalizes the Stanley-Stembridge conjecture. There is ample support for these e-positivity conjectures, including weaker positivity results in other symmetric function bases. In the first part of this thesis, we extend the work of Shareshian and Wachs from labeled graphs to a wider class of graphs, namely directed graphs. We introduce the notion of chromatic quasisymmetric function of a directed graph. For acyclic digraphs, our definition is equivalent to that of Shareshian and Wachs. We give an expansion in terms of Gessel’s fundamental quasisymmetric function basis for the chromatic quasisymmetric function of all digraphs, which shows that all the coefficients are nonnegative. We use this expansion to derive a power sum symmetric function basis expansion with positive coefficients for the chromatic quasisymmetric function of all digraphs whose chromatic quasisymmetric function has symmetric function coefficients. We describe a class of digraphs, which we call circular indifference digraphs, and show that their chromatic quasisymmetric functions are symmetric. These circular indifference digraphs include the directed cycle, for which we provide an e-basis generating function formula that shows that its chromatic quasisymmetric function is e-positive. We generalize the e-positivity conjecture of Shareshian and Wachs to the class of circular indifference digraphs. Our positivity results and computer calculations provide evidence for this conjecture. A Smirnov word is a word over the positive integers such that consecutive letters are distinct. The descent enumerator of Smirnov words is equivalent to the chromatic quasisymmetric function of the path graph. Shareshian and Wachs found a nice ebasis generating function expansion of this descent enumerator that shows that it is e-positive. Specializing this result gave them a q-analog of Euler’s exponential generating function of the classical Eulerian polynomials. In the second part of this thesis, we consider descent enumerators for restricted Smirnov words, where we put restrictions on the relationship between the first and last letter. We also consider cyclic descent enumerators for Smirnov words. Our work on these descent enumerators refines our work on the chromatic quasisymmetric function of the directed cycle. We… Advisors/Committee Members: Michelle L. Wachs, Richard P. Stanley, Bruno Benedetti, Rafael Nepomechie.

Subjects/Keywords: symmetric function; graph coloring; chromatic polynomial; directed graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Ellzey, B. (2018). On Chromatic Quasisymmetric Functions of Directed Graphs. (Doctoral Dissertation). University of Miami. Retrieved from https://scholarlyrepository.miami.edu/oa_dissertations/2091

Chicago Manual of Style (16^th Edition):

Ellzey, Brittney. “On Chromatic Quasisymmetric Functions of Directed Graphs.” 2018. Doctoral Dissertation, University of Miami. Accessed December 09, 2019. https://scholarlyrepository.miami.edu/oa_dissertations/2091.

MLA Handbook (7^th Edition):

Ellzey, Brittney. “On Chromatic Quasisymmetric Functions of Directed Graphs.” 2018. Web. 09 Dec 2019.

Vancouver:

Ellzey B. On Chromatic Quasisymmetric Functions of Directed Graphs. [Internet] [Doctoral dissertation]. University of Miami; 2018. [cited 2019 Dec 09]. Available from: https://scholarlyrepository.miami.edu/oa_dissertations/2091.

Council of Science Editors:

Ellzey B. On Chromatic Quasisymmetric Functions of Directed Graphs. [Doctoral Dissertation]. University of Miami; 2018. Available from: https://scholarlyrepository.miami.edu/oa_dissertations/2091

20. Curado, Manuel. Structural Similarity: Applications to Object Recognition and Clustering .

Degree: 2018, University of Alicante

URL: http://hdl.handle.net/10045/98110

► In this thesis, we propose many developments in the context of Structural Similarity. We address both node (local) similarity and graph (global) similarity. Concerning node… (more)

▼ In this thesis, we propose many developments in the context of Structural Similarity. We address both node (local) similarity and graph (global) similarity. Concerning node similarity, we focus on improving the diffusive process leading to compute this similarity (e.g. Commute Times) by means of modifying or rewiring the structure of the graph (Graph Densification), although some advances in Laplacian-based ranking are also included in this document. Graph Densification is a particular case of what we call graph rewiring, i.e. a novel field (similar to image processing) where input graphs are rewired to be better conditioned for the subsequent pattern recognition tasks (e.g. clustering). In the thesis, we contribute with an scalable an effective method driven by Dirichlet processes. We propose both a completely unsupervised and a semi-supervised approach for Dirichlet densification. We also contribute with new random walkers (Return Random Walks) that are useful structural filters as well as asymmetry detectors in directed brain networks used to make early predictions of Alzheimer's disease (AD). Graph similarity is addressed by means of designing structural information channels as a means of measuring the Mutual Information between graphs. To this end, we first embed the graphs by means of Commute Times. Commute times embeddings have good properties for Delaunay triangulations (the typical representation for Graph Matching in computer vision). This means that these embeddings can act as encoders in the channel as well as decoders (since they are invertible). Consequently, structural noise can be modelled by the deformation introduced in one of the manifolds to fit the other one. This methodology leads to a very high discriminative similarity measure, since the Mutual Information is measured on the manifolds (vectorial domain) through copulas and bypass entropy estimators. This is consistent with the methodology of decoupling the measurement of graph similarity in two steps: a) linearizing the Quadratic Assignment Problem (QAP) by means of the embedding trick, and b) measuring similarity in vector spaces. The QAP problem is also investigated in this thesis. More precisely, we analyze the behaviour of m-best Graph Matching methods. These methods usually start by a couple of best solutions and then expand locally the search space by excluding previous clamped variables. The next variable to clamp is usually selected randomly, but we show that this reduces the performance when structural noise arises (outliers). Alternatively, we propose several heuristics for spanning the search space and evaluate all of them, showing that they are usually better than random selection. These heuristics are particularly interesting because they exploit the structure of the affinity matrix. Efficiency is improved as well. Concerning the application domains explored in this thesis we focus on object recognition (graph similarity), clustering (rewiring), compression/decompression of graphs (links with Extremal Graph Theory), 3D shape… Advisors/Committee Members: Escolano, Francisco (advisor), Sáez Martínez, Juan Manuel (advisor).

Subjects/Keywords: Graph densification; Cut similarity; Spectral clustering; Dirichlet problems; Random walkers; Commute Times; Graph algorithms; Regular Partition; Szemeredi; Alzheimer's disease; Graphs; Return Random Walk; Net4lap; Directed graphs; Spectral graph theory; Graph entropy; Mutual information; Manifold alignment; m-Best Graph Matching; Binary-Tree Partitions; QAP; Graph sparsification; Shape simplification; Alpha shapes

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Curado, M. (2018). Structural Similarity: Applications to Object Recognition and Clustering . (Thesis). University of Alicante. Retrieved from http://hdl.handle.net/10045/98110

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Curado, Manuel. “Structural Similarity: Applications to Object Recognition and Clustering .” 2018. Thesis, University of Alicante. Accessed December 09, 2019. http://hdl.handle.net/10045/98110.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Curado, Manuel. “Structural Similarity: Applications to Object Recognition and Clustering .” 2018. Web. 09 Dec 2019.

Vancouver:

Curado M. Structural Similarity: Applications to Object Recognition and Clustering . [Internet] [Thesis]. University of Alicante; 2018. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10045/98110.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Curado M. Structural Similarity: Applications to Object Recognition and Clustering . [Thesis]. University of Alicante; 2018. Available from: http://hdl.handle.net/10045/98110

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

KTH

21. Aspegren, Villiam. CluStic – Automatic graph drawing with clusters.

Degree: Computer Science and Communication (CSC), 2015, KTH

URL: http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-179251

►

<h2>Abstract</h2> Finding a visually pleasing layout from a set of vertices and edges is the goal of automatic graph drawing. A requirement that has been… (more)

▼

<h2>Abstract</h2> Finding a visually pleasing layout from a set of vertices and edges is the goal of automatic graph drawing. A requirement that has been barely explored however, is that users would like to specify portions of their layouts that are not altered by such algorithms. For example the user may have put a lot of manual effort into fixing a portion of a large layout and, while they would like an automatic layout applied to most of the layout, they do not want their work undone on the portion they manually fixed earlier. CluStic, the system developed and evaluated in this thesis, provides this capability. CluStic maintain the internal structure of a cluster by giving it priority over other elements in the graph. After high priority element has been positioned, non-priority vertices may be placed at the most appropriate remaining positions. Furthermore CluStic produces layouts which also maintain common aesthetic criteria: edge crossing minimization, layout height and edge straightening. Our method in this thesis is to first conduct an initial exploration study where we cross compare four industrial tools: Cytogate, GraphDraw, Diagram.Net and GraphNet. A set of layouts are generated with these tools and the user is timed on a task to identify the longest path. Through this exploration study we develop out intuition and determined that Cytogate is the best performing tool for longest path identification. Given this experience we fully develop CluStic and conduct our main study where we cross compare it with Cytogate and a baseline Breadth-first Search algorithm. Results show that CluStic produces drawings of good quality, Clustic achieves a visualization efficiency score of 1,4 which is an increase compared to the BFS layout (-3,8). CluStic is outperformed by Cytogate which achieves a visualization efficiency score of 1,9 and therefore produces less visually pleasing drawings. However Clustic, unlike Cytogate can preserve initial static structures, thus when a graph contains elements in which their position cannot be altered CluStic is a better choice.

<h2>Referat</h2> Målet med automatiserad grafritning är att utifrån en uppsättning noder och kanter hitta en layout som är visuellt tillfredställande. Ett delområde som inte utforskats nog är möjligheten till att låsa vissa komponenter i grafen som sedan inte får alterneras av grafritningsalgoritmen. En användare som exempel, strukturerar vissa delar av grafen manuellt och applicerar sedan automatisk layout av resterande element utan att förstöra den struktur som manuellt skapats. CluStic, grafritningsverktyget som skapats och utvärderats i denna masters uppsats fyller denna funktion. CluStic bevarar den interna strukturen för ett kluster genom att tilldela en högre prioritet för noder i klustret med avseende på övriga element i grafen. Efter att högprioritets element placerats tilldelas resterande element sina bäst tillgängliga positioner. Utöver detta så uppfyller CluStic några av de vanligaste estetiska mål inom grafritning: minimera antalet…

Subjects/Keywords: Graph drawing; Automatic graph layout; Directed graphs; Sugiyama; Cluster; Clusters; Computer Sciences; Datavetenskap (datalogi)

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Aspegren, V. (2015). CluStic – Automatic graph drawing with clusters. (Thesis). KTH. Retrieved from http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-179251

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Aspegren, Villiam. “CluStic – Automatic graph drawing with clusters.” 2015. Thesis, KTH. Accessed December 09, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-179251.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Aspegren, Villiam. “CluStic – Automatic graph drawing with clusters.” 2015. Web. 09 Dec 2019.

Vancouver:

Aspegren V. CluStic – Automatic graph drawing with clusters. [Internet] [Thesis]. KTH; 2015. [cited 2019 Dec 09]. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-179251.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Aspegren V. CluStic – Automatic graph drawing with clusters. [Thesis]. KTH; 2015. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-179251

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Alberta

22. Enright, Jessica Anne. Results on Set Representations of Graphs.

Degree: PhD, Department of Computing Science, 2011, University of Alberta

URL: https://era.library.ualberta.ca/files/41687k094

► A set representation of a graph is an assignment of sets to vertices such that two vertices are adjacent if and only if their assigned… (more)

Subjects/Keywords: intersection graphs; combinatorial games; graph theory

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Enright, J. A. (2011). Results on Set Representations of Graphs. (Doctoral Dissertation). University of Alberta. Retrieved from https://era.library.ualberta.ca/files/41687k094

Chicago Manual of Style (16^th Edition):

Enright, Jessica Anne. “Results on Set Representations of Graphs.” 2011. Doctoral Dissertation, University of Alberta. Accessed December 09, 2019. https://era.library.ualberta.ca/files/41687k094.

MLA Handbook (7^th Edition):

Enright, Jessica Anne. “Results on Set Representations of Graphs.” 2011. Web. 09 Dec 2019.

Vancouver:

Enright JA. Results on Set Representations of Graphs. [Internet] [Doctoral dissertation]. University of Alberta; 2011. [cited 2019 Dec 09]. Available from: https://era.library.ualberta.ca/files/41687k094.

Council of Science Editors:

Enright JA. Results on Set Representations of Graphs. [Doctoral Dissertation]. University of Alberta; 2011. Available from: https://era.library.ualberta.ca/files/41687k094

Hong Kong University of Science and Technology

23. Abeynayake, Hiddadura Isura Malinda Mendis. Effectiveness of static data representation.

Degree: 2016, Hong Kong University of Science and Technology

URL: https://doi.org/10.14711/thesis-b1584484 ; http://repository.ust.hk/ir/bitstream/1783.1-80395/1/th_redirect.html

► Graphs are a means to convey the numerical information in day to day life so that they can be seeing and understood. Effective ways to… (more)

Subjects/Keywords: Information visualization; Representations of graphs; Graph theory

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Abeynayake, H. I. M. M. (2016). Effectiveness of static data representation. (Thesis). Hong Kong University of Science and Technology. Retrieved from https://doi.org/10.14711/thesis-b1584484 ; http://repository.ust.hk/ir/bitstream/1783.1-80395/1/th_redirect.html

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Abeynayake, Hiddadura Isura Malinda Mendis. “Effectiveness of static data representation.” 2016. Thesis, Hong Kong University of Science and Technology. Accessed December 09, 2019. https://doi.org/10.14711/thesis-b1584484 ; http://repository.ust.hk/ir/bitstream/1783.1-80395/1/th_redirect.html.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Abeynayake, Hiddadura Isura Malinda Mendis. “Effectiveness of static data representation.” 2016. Web. 09 Dec 2019.

Vancouver:

Abeynayake HIMM. Effectiveness of static data representation. [Internet] [Thesis]. Hong Kong University of Science and Technology; 2016. [cited 2019 Dec 09]. Available from: https://doi.org/10.14711/thesis-b1584484 ; http://repository.ust.hk/ir/bitstream/1783.1-80395/1/th_redirect.html.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Abeynayake HIMM. Effectiveness of static data representation. [Thesis]. Hong Kong University of Science and Technology; 2016. Available from: https://doi.org/10.14711/thesis-b1584484 ; http://repository.ust.hk/ir/bitstream/1783.1-80395/1/th_redirect.html

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Waterloo

24. Sato, Cristiane Maria. Core Structures in Random Graphs and Hypergraphs.

Degree: 2013, University of Waterloo

URL: http://hdl.handle.net/10012/7787

► The k-core of a graph is its maximal subgraph with minimum degree at least k. The study of k-cores in random graphs was initiated by… (more)

Subjects/Keywords: combinatorics; graph theory; random graphs; probabilistic; enumeration

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Sato, C. M. (2013). Core Structures in Random Graphs and Hypergraphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/7787

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Sato, Cristiane Maria. “Core Structures in Random Graphs and Hypergraphs.” 2013. Thesis, University of Waterloo. Accessed December 09, 2019. http://hdl.handle.net/10012/7787.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Sato, Cristiane Maria. “Core Structures in Random Graphs and Hypergraphs.” 2013. Web. 09 Dec 2019.

Vancouver:

Sato CM. Core Structures in Random Graphs and Hypergraphs. [Internet] [Thesis]. University of Waterloo; 2013. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10012/7787.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Sato CM. Core Structures in Random Graphs and Hypergraphs. [Thesis]. University of Waterloo; 2013. Available from: http://hdl.handle.net/10012/7787

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of California – San Diego

25. Tobin, Robin Joshua. Extremal Spectral Invariants of Graphs.

Degree: Mathematics, 2017, University of California – San Diego

URL: http://www.escholarship.org/uc/item/8pw2j45q

► We address several problems in spectral graph theory, with a common theme of optimizing or computing a spectral graph invariant, such as the spectral radius… (more)

Subjects/Keywords: Mathematics; graph theory; planar graphs; spectral graph theory

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Tobin, R. J. (2017). Extremal Spectral Invariants of Graphs. (Thesis). University of California – San Diego. Retrieved from http://www.escholarship.org/uc/item/8pw2j45q

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Tobin, Robin Joshua. “Extremal Spectral Invariants of Graphs.” 2017. Thesis, University of California – San Diego. Accessed December 09, 2019. http://www.escholarship.org/uc/item/8pw2j45q.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Tobin, Robin Joshua. “Extremal Spectral Invariants of Graphs.” 2017. Web. 09 Dec 2019.

Vancouver:

Tobin RJ. Extremal Spectral Invariants of Graphs. [Internet] [Thesis]. University of California – San Diego; 2017. [cited 2019 Dec 09]. Available from: http://www.escholarship.org/uc/item/8pw2j45q.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Tobin RJ. Extremal Spectral Invariants of Graphs. [Thesis]. University of California – San Diego; 2017. Available from: http://www.escholarship.org/uc/item/8pw2j45q

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Waterloo

26. Lee, Edward. Circle Graph Obstructions.

Degree: 2017, University of Waterloo

URL: http://hdl.handle.net/10012/12309

In this thesis we present a self-contained proof of Bouchet’s characterization of the class of circle graphs. The proof uses signed graphs and is analogous to Gerards’ graphic proof of Tutte’s excluded-minor characterization of the class of graphic matroids.

Subjects/Keywords: Circle Graphs; Structural Graph Theory; Graph Theory; Vertex Minors

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Lee, E. (2017). Circle Graph Obstructions. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/12309

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Lee, Edward. “Circle Graph Obstructions.” 2017. Thesis, University of Waterloo. Accessed December 09, 2019. http://hdl.handle.net/10012/12309.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Lee, Edward. “Circle Graph Obstructions.” 2017. Web. 09 Dec 2019.

Vancouver:

Lee E. Circle Graph Obstructions. [Internet] [Thesis]. University of Waterloo; 2017. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10012/12309.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Lee E. Circle Graph Obstructions. [Thesis]. University of Waterloo; 2017. Available from: http://hdl.handle.net/10012/12309

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Univerzitet u Beogradu

27. Mihailović, Bojana Lj., 1960-. Neke klase grafova sa datim ograničenjima druge sopstvene vrednosti.

Degree: Matematički fakultet, 2017, Univerzitet u Beogradu

URL: https://fedorabg.bg.ac.rs/fedora/get/o:15171/bdef:Content/get

►

Matematika - Spektralna teorija grafova / Mathematics - Spectral graph theory

Predmet ove disertacije pripada oblasti spektralne teorije grafova, mladoj grani matematičke kombinatorike, odnosno teorije… (more)

▼

Matematika - Spektralna teorija grafova / Mathematics - Spectral graph theory

Predmet ove disertacije pripada oblasti spektralne teorije grafova, mladoj grani matematičke kombinatorike, odnosno teorije grafova, koja u današnje vreme nalazi važne primene u mnogim poljima, kao što su hemija, fizika, računarstvo, telekomunikacije, sociologija, itd. kao i razne oblasti matematike. Spektralna teorija grafova dovodi u vezu osnovne osobine i strukturu grafa sa osobinama spektra njegovih matrica (matrice susedstva, Laplasove matrice itd.). U ovoj disertaciji reč je isključivo o spektru matrice susedstva grafa. Druga po veličini sopstvena vrednost matrice susedstva grafa (kraće, druga sopstvena vrednost grafa), kao i njeno rastojanje od najveće sopstvene vrednosti, od značaja su naročito za primenu spektralne teorije u računarstvu. Osobina grafa da mu posmatrana sopstvena vrednost ne prevazilazi dato ograničenje jeste nasledna osobina, pa su mnoga istraživanja o ovakvim ograničenjima išla u pravcu nalaženja maksimalnih dozvoljenih grafova ili nalaženja minimalnih zabranjenih grafova za tu osobinu. Ova disertacija bavi se određivanjem nekih klasa grafova koje imaju dato ograničenje druge sopstvene vrednosti matrice susedstva grafa i u tom cilju razvija neke vrlo korisne instrumente. U metodološkom smislu istraživanja u ovoj disertaciji predstavljaju spregu primene algebarskog aparata i metoda spektralne teorije grafova i kombinatorog rezonovanja, dok je u pojedinim fazama korišćen i ekspertni sistem newGRAPH. Disertacija sadrži osam glava, koje su podeljene na delove. Na početku se navode prethodni rezultati, a zatim se uvode i razvijaju novi i originalni elementi algebarsko-kombinatornog aparata koji ubrzava i olakšava dalji rad. Definišu se preslikavanja između određenih familija grafova, od kojih neka čuvaju znak izraza λ2 - 2 i pomoću njih se opisuju i sistematizuju neki već poznati rezultati na nov način. Zatim se u potpunosti određuju svi maksimalni refleksivni triciklički kaktusi koji nisu RS-odlučivi i čije konture ne čine snop iz klasa R1 i R3 i daju parcijalni rezultati koji se tiču klase R2 , uz primenu prethodno uvedenih preslikavanja (dosad su u potpunosti bili određeni samo oni iz preostale klase R4 [40], [46]). Dalje se kompletno opisuju svi minimalni zabranjeni grafovi u klasi bicikličkih grafova sa mostom i svi minimalni zabranjeni grafovi u klasi R3 - pristup koji kod refleksivnih grafova još nije bio korišćen. Zatim se određuje maksimalan broj kontura za RS-neodlučive refleksivne kaktuse za slučaj kad konture sadrže snop, a time i uopšte za RS-neodlučive refleksivne kaktuse, i opisuju tri klase maksimalnih refleksivnih RS-neodlučivih kaktusa koji sadrže snop kontura. Posle toga su uopšteni neki prethodni rezultati: iskazano je i dokazano uopštenje RS-teoreme (tzv. GRS-teorema) za bilo koje r, r > 0 ; uopštena su prethodno uvedena preslikavanja, dokazane su osobine uopštenja i dati različiti primeri klasa grafova sa osobinom λ2 <r (za r > 0 ). Na osnovu prethodnog, opisani su svi GRSneodlučivi maksimalni…

Advisors/Committee Members: Radosavljević, Zoran, 1949-.

Subjects/Keywords: spectral graph theory; second largest eigenvalue; hereditary graph property; maximal graphs; minimal forbidden graphs; treelike graphs (cacti); reflexive graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Mihailović, Bojana Lj., 1. (2017). Neke klase grafova sa datim ograničenjima druge sopstvene vrednosti. (Thesis). Univerzitet u Beogradu. Retrieved from https://fedorabg.bg.ac.rs/fedora/get/o:15171/bdef:Content/get

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Mihailović, Bojana Lj., 1960-. “Neke klase grafova sa datim ograničenjima druge sopstvene vrednosti.” 2017. Thesis, Univerzitet u Beogradu. Accessed December 09, 2019. https://fedorabg.bg.ac.rs/fedora/get/o:15171/bdef:Content/get.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Mihailović, Bojana Lj., 1960-. “Neke klase grafova sa datim ograničenjima druge sopstvene vrednosti.” 2017. Web. 09 Dec 2019.

Vancouver:

Mihailović, Bojana Lj. 1. Neke klase grafova sa datim ograničenjima druge sopstvene vrednosti. [Internet] [Thesis]. Univerzitet u Beogradu; 2017. [cited 2019 Dec 09]. Available from: https://fedorabg.bg.ac.rs/fedora/get/o:15171/bdef:Content/get.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Mihailović, Bojana Lj. 1. Neke klase grafova sa datim ograničenjima druge sopstvene vrednosti. [Thesis]. Univerzitet u Beogradu; 2017. Available from: https://fedorabg.bg.ac.rs/fedora/get/o:15171/bdef:Content/get

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Illinois – Urbana-Champaign

28. Samotij, Wojciech. Extremal problems in pseudo-random graphs and asymptotic enumeration.

Degree: PhD, 0439, 2010, University of Illinois – Urbana-Champaign

URL: http://hdl.handle.net/2142/15574

► This dissertation tackles several questions in extremal graph theory and the theory of random graphs. It consists of three more or less independent parts that… (more)

▼ This dissertation tackles several questions in extremal graph theory and the theory of random graphs. It consists of three more or less independent parts that all fit into one bigger picture – the meta-problem of describing the structure and properties of large random and pseudo-random graphs. Given a positive constant c, we call an n-vertex graph G c-Ramsey if G does not contain a clique or an independent set of size greater than c*log(n). Since all of the known examples of Ramsey graphs come from various constructions employing randomness, several researchers have conjectured that all Ramsey graphs possess certain pseudo-random properties. We study one such question – a conjecture of Erdos, Faudree, and Sos regarding the orders and sizes of induced subgraphs of Ramsey graphs. Although we do not fully resolve this conjecture, the main theorem in the first part of this dissertation, joint work with Noga Alon, Jozsef Balogh, and Alexandr Kostochka, significantly improves the previous state-of-the-art result of Alon and Kostochka. For a positive integer n and a real number p in [0,1], one defines the Erdos-Renyi random graph G(n,p) to be the probability distribution on the set of all graphs on the vertex set {1,...,n} such that the probability that a particular pair {i,j} of vertices is an edge in G(n,p) is p, independently of all other pairs. In the second part of this dissertation, we study the behavior of the random graph G(n,p) with respect to the property of containing large trees with bounded maximum degree. Our first main theorem, joint work with Jozsef Balogh, Bela Csaba, and Martin Pei, gives a sufficient condition on p to imply that with probability tending to 1 as n tends to infinity, G(n,p) contains all almost spanning trees with bounded maximum degree, improving a previous result of Alon, Krivelevich, and Sudakov. In the second main theorem of this part, joint work with Jozsef Balogh and Bela Csaba, we show that G(n,p) almost surely contains all almost spanning trees with bounded maximum degree even after an adversary removes asymptotically half of the edges in G(n,p). Given an arbitrary graph H, we say that a graph G is H-free if G does not contain H as a subgraph. Edros, Frankl, and Rodl generalized a famous theorem of Erdos and Stone by proving that for every non-bipartite H, the number of labeled H-free graphs on a fixed n-vertex set, f_n(H), satisfies log_2f_n(H) < (1+o(1))ex(n,H). The case when H is bipartite has proved to be much harder. For all such H, apart from the cycles of length 4 and 6, it is not even known whether log_2f_n(H) < C*ex(n,H). The main result of the last part of this thesis, joint work with Jozsef Balogh, proves such a bound for `almost all' complete bipartite graphs. This result and the methods used to prove it have many interesting applications, some of which we study in the last chapter. Advisors/Committee Members: Balogh, József (advisor), West, Douglas B. (Committee Chair), Kostochka, Alexandr V. (committee member), Balogh, József (committee member), Vijay, Sujith (committee member).

Subjects/Keywords: combinatorics; graphs; graph theory; Extremal Graph Theory; probability; random; pseudo-random; quasi-random; random graphs; pseudo-random graphs; Ramsey; Ramsey theory

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Samotij, W. (2010). Extremal problems in pseudo-random graphs and asymptotic enumeration. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/15574

Chicago Manual of Style (16^th Edition):

Samotij, Wojciech. “Extremal problems in pseudo-random graphs and asymptotic enumeration.” 2010. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed December 09, 2019. http://hdl.handle.net/2142/15574.

MLA Handbook (7^th Edition):

Samotij, Wojciech. “Extremal problems in pseudo-random graphs and asymptotic enumeration.” 2010. Web. 09 Dec 2019.

Vancouver:

Samotij W. Extremal problems in pseudo-random graphs and asymptotic enumeration. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2010. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/2142/15574.

Council of Science Editors:

Samotij W. Extremal problems in pseudo-random graphs and asymptotic enumeration. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2010. Available from: http://hdl.handle.net/2142/15574

Indian Institute of Science

29. Basavaraju, Manu. Acyclic Edge Coloring Of Graphs.

Degree: 2010, Indian Institute of Science

URL: http://hdl.handle.net/2005/2263

► A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e)… (more)

▼ A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e) ≠ c(ƒ) for any adjacent edges e,f. The minimum number of colors needed to properly color the edges of G, is called the chromatic index of Gand is denoted by χ(G). A proper edge coloring c is called acyclic if there are no bichromatic cycles in the graph. In other words an edge coloring is acyclic if the union of any two color classes induces a set of paths (i.e., linear forest) in G. The acyclic edge chromatic number (also called acyclic chromatic index), denoted by a’(G), is the minimum number of colors required to acyclically edge color G. The primary motivation for this thesis is the following conjecture by Alon, Sudakov and Zaks [7] (and independently by Fiamcik [22]): Acyclic Edge Coloring Conjecture: For any graph G, a’ (G) ≤ Δ(G)+2. The following are the main results of the thesis: 1 From a result of Burnstein [16], it follows that any subcubic graph can be acyclically edge colored using at most 5 colors. Skulrattankulchai [38] gave a polynomial time algorithm to color a subcubic graph using Δ + 2 = 5 colors. We proved that any non-regular subcubic graph can be acyclically colored using only 4 colors. This result is tight. This also implies that the fifth color, when needed is required only for one edge. 2 Let G be a connected graph on n vertices, m ≤ 2n - 1 edges and maximum degree Δ ≤ 4, then a’ (G) ≤ 6. This implies that graph of maximum degree 4 are acyclically edge colorable using at most 7 colors. 3 The earliest result on acyclic edge coloring of 2-degenerate graphs was by Caro and Roditty [17], where they proved that a’ (G) ≤ Δ + k - 1, where k is the maximum edge connectivity, defined as k = maxu,vε V(G)λ(u,v), where λ(u,v)is the edge-connectivity of the pair u,v. Note that here k can be as high as Δ. Muthu,Narayanan and Subramanian [34] proved that a’ (G) ≤ Δ + 1for outerplanar graphs which are a subclass of 2-degenerate graphs and posed the problem of proving the conjecture for 2-degenerate graphs as an open problem. In fact they have also derived an upper bound of Δ+1 for series-parallel graphs [35], which is a slightly bigger subclass of 2-degenerate graphs. We proved that 2-degenerate graphs are Δ+1colorable. 1 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of 2Δ+29 for planar graphs. Independently Hou, Wu, GuiZhen Liu and Bin Liu [29] gave an upper bound of max(2Δ - 2,Δ+ 22). We improve this upper bound to Δ+12, which is the best known bound at present. 2 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of Δ+6for triangle free planar graphs. We improve the bound to Δ+3, which is the best known bound at present. 3 We have also worked on lower bounds. Alon et.al. [7], along with the acyclic edge coloring conjecture, also made an auxiliary conjecture stating that Complete graphs of 2n vertices are the only class of regular graphs which require Δ+2colors. We disproved this conjecture by showing infinite classes of regular graphs other than Complete Graphs… Advisors/Committee Members: Chandran, L Sunil.

Subjects/Keywords: Graph - Coloring; Graph Theory; Graphs - Acyclic Edge Coloring; Subcubic Graphs; 2-Degenerate Graphs; Planar Graphs; Acyclic Edge Coloring; Dense Graphs; Graph Theory

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Basavaraju, M. (2010). Acyclic Edge Coloring Of Graphs. (Thesis). Indian Institute of Science. Retrieved from http://hdl.handle.net/2005/2263

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Basavaraju, Manu. “Acyclic Edge Coloring Of Graphs.” 2010. Thesis, Indian Institute of Science. Accessed December 09, 2019. http://hdl.handle.net/2005/2263.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Basavaraju, Manu. “Acyclic Edge Coloring Of Graphs.” 2010. Web. 09 Dec 2019.

Vancouver:

Basavaraju M. Acyclic Edge Coloring Of Graphs. [Internet] [Thesis]. Indian Institute of Science; 2010. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/2005/2263.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Basavaraju M. Acyclic Edge Coloring Of Graphs. [Thesis]. Indian Institute of Science; 2010. Available from: http://hdl.handle.net/2005/2263

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Indian Institute of Science

30. Basavaraju, Manu. Acyclic Edge Coloring Of Graphs.

Degree: 2010, Indian Institute of Science

URL: http://etd.iisc.ernet.in/handle/2005/2263 ; http://etd.ncsi.iisc.ernet.in/abstracts/2885/G24692-Abs.pdf

► A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e)… (more)

▼ A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e) ≠ c(ƒ) for any adjacent edges e,f. The minimum number of colors needed to properly color the edges of G, is called the chromatic index of Gand is denoted by χ(G). A proper edge coloring c is called acyclic if there are no bichromatic cycles in the graph. In other words an edge coloring is acyclic if the union of any two color classes induces a set of paths (i.e., linear forest) in G. The acyclic edge chromatic number (also called acyclic chromatic index), denoted by a’(G), is the minimum number of colors required to acyclically edge color G. The primary motivation for this thesis is the following conjecture by Alon, Sudakov and Zaks [7] (and independently by Fiamcik [22]): Acyclic Edge Coloring Conjecture: For any graph G, a’ (G) ≤ Δ(G)+2. The following are the main results of the thesis: 1 From a result of Burnstein [16], it follows that any subcubic graph can be acyclically edge colored using at most 5 colors. Skulrattankulchai [38] gave a polynomial time algorithm to color a subcubic graph using Δ + 2 = 5 colors. We proved that any non-regular subcubic graph can be acyclically colored using only 4 colors. This result is tight. This also implies that the fifth color, when needed is required only for one edge. 2 Let G be a connected graph on n vertices, m ≤ 2n - 1 edges and maximum degree Δ ≤ 4, then a’ (G) ≤ 6. This implies that graph of maximum degree 4 are acyclically edge colorable using at most 7 colors. 3 The earliest result on acyclic edge coloring of 2-degenerate graphs was by Caro and Roditty [17], where they proved that a’ (G) ≤ Δ + k - 1, where k is the maximum edge connectivity, defined as k = maxu,vε V(G)λ(u,v), where λ(u,v)is the edge-connectivity of the pair u,v. Note that here k can be as high as Δ. Muthu,Narayanan and Subramanian [34] proved that a’ (G) ≤ Δ + 1for outerplanar graphs which are a subclass of 2-degenerate graphs and posed the problem of proving the conjecture for 2-degenerate graphs as an open problem. In fact they have also derived an upper bound of Δ+1 for series-parallel graphs [35], which is a slightly bigger subclass of 2-degenerate graphs. We proved that 2-degenerate graphs are Δ+1colorable. 1 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of 2Δ+29 for planar graphs. Independently Hou, Wu, GuiZhen Liu and Bin Liu [29] gave an upper bound of max(2Δ - 2,Δ+ 22). We improve this upper bound to Δ+12, which is the best known bound at present. 2 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of Δ+6for triangle free planar graphs. We improve the bound to Δ+3, which is the best known bound at present. 3 We have also worked on lower bounds. Alon et.al. [7], along with the acyclic edge coloring conjecture, also made an auxiliary conjecture stating that Complete graphs of 2n vertices are the only class of regular graphs which require Δ+2colors. We disproved this conjecture by showing infinite classes of regular graphs other than Complete Graphs… Advisors/Committee Members: Chandran, L Sunil.

Subjects/Keywords: Graph - Coloring; Graph Theory; Graphs - Acyclic Edge Coloring; Subcubic Graphs; 2-Degenerate Graphs; Planar Graphs; Acyclic Edge Coloring; Dense Graphs; Graph Theory

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Basavaraju, M. (2010). Acyclic Edge Coloring Of Graphs. (Thesis). Indian Institute of Science. Retrieved from http://etd.iisc.ernet.in/handle/2005/2263 ; http://etd.ncsi.iisc.ernet.in/abstracts/2885/G24692-Abs.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Basavaraju, Manu. “Acyclic Edge Coloring Of Graphs.” 2010. Thesis, Indian Institute of Science. Accessed December 09, 2019. http://etd.iisc.ernet.in/handle/2005/2263 ; http://etd.ncsi.iisc.ernet.in/abstracts/2885/G24692-Abs.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Basavaraju, Manu. “Acyclic Edge Coloring Of Graphs.” 2010. Web. 09 Dec 2019.

Vancouver:

Basavaraju M. Acyclic Edge Coloring Of Graphs. [Internet] [Thesis]. Indian Institute of Science; 2010. [cited 2019 Dec 09]. Available from: http://etd.iisc.ernet.in/handle/2005/2263 ; http://etd.ncsi.iisc.ernet.in/abstracts/2885/G24692-Abs.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Basavaraju M. Acyclic Edge Coloring Of Graphs. [Thesis]. Indian Institute of Science; 2010. Available from: http://etd.iisc.ernet.in/handle/2005/2263 ; http://etd.ncsi.iisc.ernet.in/abstracts/2885/G24692-Abs.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

		in
And / Or
		in
And / Or
		in
And / Or
		in

Open Access Theses and Dissertations