You searched for subject:(Graphs).
Showing records 1 – 30 of
1853 total matches.
◁ [1] [2] [3] [4] [5] … [62] ▶
1.
Arvind, N R.
Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -.
Degree: Mathematical Science, 2010, INFLIBNET
URL: http://shodhganga.inflibnet.ac.in/handle/10603/4726 
► This thesis deals mainly with two related coloring problems ? forbidden subgraph colorings and oriented colorings. The former deals with proper colorings of vertices or…
(more)
▼ This thesis deals mainly with two related coloring
problems ? forbidden subgraph colorings and oriented colorings. The
former deals with proper colorings of vertices or edges of a graph
with constraints on the union of color classes. A well-known
example is the acyclic vertex coloring in which we require a proper
coloring such that the union of any two color classes is acyclic.
Other wellstudied examples include the acyclic edge coloring and
star coloring. Our focus in this thesis is a generalization of
these special types of colorings. Oriented coloring deals with
colorings of oriented graphs (directed graphs obtained by orienting
each edge of a simple undirected graph). Specifically, an oriented
coloring is a homomorphism to an oriented graph, the vertices of
the target graph being considered as the colors assigned to the
vertices of the source graph. For both of these problems, we want
to find good upper bounds for the number of colors required for
such colorings. In this thesis, we find upper bounds for forbidden
subgraph chromatic numbers in terms of the maximum degree. For the
union of two color classes, we show the asymptotic tightness of our
bounds by a probabilistic contstruction. We then show that the
oriented chromatic number of a graph can be bounded in terms of the
forbidden subgraph chromatic numbers. In conjunction with our
afore-mentioned results, this allowed us to prove improved bounds
on oriented chromatic numbers of graphs on surfaces. Specifically,
we obtained the following results: ? Given a family F of connected
graphs each having at least m edges, the vertices of any graph
ofmaximum degree _ can be properly colored using O(_1+ 1
mand#8722;1 ) colors so that in the union of any 2 color classes,
there is no copy of H for any H and#8712; F. ? Any graph of genus g
has oriented chromatic number at most 2g1/2+o(1) . We also consider
edge colorings of graphs with restrictions on the union of color
classes. While edge colorings can simply be considered as vertex
colorings of the line graph.
Bibilography p.95-101
Advisors/Committee Members: Balasubramanian R, Subramanian, C R.
Subjects/Keywords: Graphs; Graphs dimensions; Graphs colorings
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Arvind, N. R. (2010). Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -. (Thesis). INFLIBNET. Retrieved from http://shodhganga.inflibnet.ac.in/handle/10603/4726
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Arvind, N R. “Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -.” 2010. Thesis, INFLIBNET. Accessed April 21, 2021.
http://shodhganga.inflibnet.ac.in/handle/10603/4726.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Arvind, N R. “Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -.” 2010. Web. 21 Apr 2021.
Vancouver:
Arvind NR. Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -. [Internet] [Thesis]. INFLIBNET; 2010. [cited 2021 Apr 21].
Available from: http://shodhganga.inflibnet.ac.in/handle/10603/4726.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Arvind NR. Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -. [Thesis]. INFLIBNET; 2010. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/4726
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
2.
Mozes, Shay.
Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs.
Degree: PhD, Computer Science, 2013, Brown University
URL: https://repository.library.brown.edu/studio/item/bdr:320482/
► Large graphs are ubiquitous in many diverse fields ranging from sociology and economics to biology and engineering. Applications in numerous areas such as transportation, geographical…
(more)
▼ Large
graphs are ubiquitous in many diverse fields
ranging from sociology and economics to biology and engineering.
Applications in numerous areas such as transportation, geographical
routing, computer vision and VLSI design involve solving
optimization problems on large planar
graphs. The sheer growth in
the number and size of available data sets drives a need to design
optimization algorithms that are not merely efficient in the
qualitative sense that their computational resource consumption is
polynomial in the size of the input, but in the stronger
quantitative sense that the amount of required resources
(specifically, running time and space) is as close to linear as
possible.
In this thesis we study the combinatorial structural
properties of directed planar
graphs, and exploit these properties
to devise efficient algorithms for shortest-path and maximum-flow
problems in such
graphs. Among the results we present are:
- A linear-space algorithm for the shortest-path problem in
directed planar
graphs with real (positive and negative) arc
lengths that runs in near-linear time. Our algorithm is more
efficient and conceptually simpler than previously known algorithms
for this problem.
- Data structures for efficiently reporting exact distances
in directed planar
graphs (distance oracles) with significantly
improved space-to-query-time ratio over previously known exact
distance oracles.
- A near-linear time algorithm for computing a maximum flow
in directed planar
graphs with multiple sources and sinks. This
problem has been open for more than 20 years. No planarity
exploiting algorithm for the problem was previously known. Our
algorithm is significantly faster than previous algorithms for this
problem.
These problems, and the tools and techniques used in solving
them, are interrelated.
Advisors/Committee Members: Klein, Philip (Director), Erickson, Jeff (Reader), Kelner, Jonathan (Reader), Mathieu, Claire (Reader).
Subjects/Keywords: planar graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Mozes, S. (2013). Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs. (Doctoral Dissertation). Brown University. Retrieved from https://repository.library.brown.edu/studio/item/bdr:320482/
Chicago Manual of Style (16th Edition):
Mozes, Shay. “Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs.” 2013. Doctoral Dissertation, Brown University. Accessed April 21, 2021.
https://repository.library.brown.edu/studio/item/bdr:320482/.
MLA Handbook (7th Edition):
Mozes, Shay. “Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs.” 2013. Web. 21 Apr 2021.
Vancouver:
Mozes S. Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs. [Internet] [Doctoral dissertation]. Brown University; 2013. [cited 2021 Apr 21].
Available from: https://repository.library.brown.edu/studio/item/bdr:320482/.
Council of Science Editors:
Mozes S. Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs. [Doctoral Dissertation]. Brown University; 2013. Available from: https://repository.library.brown.edu/studio/item/bdr:320482/
3.
Camarero Coterillo, Cristobal.
Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos.
Degree: 2015, Universidad de Cantabria
URL: http://hdl.handle.net/10902/6542
► ABSTRACT: The topology of a interconnection network is the graph of its routers. The topologies that are being currently used in large supercomputers can be…
(more)
▼ ABSTRACT: The topology of a interconnection network is the graph of its routers. The topologies that are being currently used in large supercomputers can be classified into two families: the ones that use routers with moderate radix and the ones using high-radix routers. The objective of this thesis is to define topologies for both families that exhibit better properties than the actual ones.
Examples of moderate degree machines are the Cray XK7, the K computer and the Blue Gene/Q, whose topologies are tori. In this thesis the lattice
graphs are proposed. They are variant of tori with reduced distances and which can be symmetric for sizes in which the tori is forced to be asymmetric.
Among the most used topologies for the family of high-radix routers there are the Clos networks, and more recently, the dragonfly networks. This thesis focuses on dragonfly networks. In this thesis, it is explained how Hamming
graphs can be seen as a dragonfly with large global trunking and that some properties of the Hamming
graphs can be extrapolated to dragonflies.
The problem of finding lattice
graphs with optimal distance properties is actually equivalent to the problem of finding good codes over the Lee space. In this thesis several quasi-perfect codes are built, which can then be seen as nearly optimal lattice
graphs. They include quasi-perfect codes for arbitrarily large dimensions that reach half the density of the density of potential perfect Lee.
Advisors/Committee Members: Martínez Fernández, María del Carmen (advisor), Universidad de Cantabria (other).
Subjects/Keywords: Graphs
…brings the
definition of lattice graphs, which actually contains all Cayley graphs over Abelian… …used
in crystallography. When these are used to define lattice graphs, good properties are… …machines. From the properties of these crystal lattice graphs the symmetry is
very notable; it is… …obtained that symmetric lattice graphs have better performance than
the asymmetric ones. This… …implement them in
racks. Although there are known families of graphs with better distance…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Camarero Coterillo, C. (2015). Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos. (Doctoral Dissertation). Universidad de Cantabria. Retrieved from http://hdl.handle.net/10902/6542
Chicago Manual of Style (16th Edition):
Camarero Coterillo, Cristobal. “Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos.” 2015. Doctoral Dissertation, Universidad de Cantabria. Accessed April 21, 2021.
http://hdl.handle.net/10902/6542.
MLA Handbook (7th Edition):
Camarero Coterillo, Cristobal. “Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos.” 2015. Web. 21 Apr 2021.
Vancouver:
Camarero Coterillo C. Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos. [Internet] [Doctoral dissertation]. Universidad de Cantabria; 2015. [cited 2021 Apr 21].
Available from: http://hdl.handle.net/10902/6542.
Council of Science Editors:
Camarero Coterillo C. Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos. [Doctoral Dissertation]. Universidad de Cantabria; 2015. Available from: http://hdl.handle.net/10902/6542
University of Florida
4.
Alipanahi Ramandi, Bahareh.
Variants and Applications of Colored De Bruijn Graphs.
Degree: PhD, Computer Science - Computer and Information Science and Engineering, 2020, University of Florida
URL: https://ufdc.ufl.edu/UFE0056439
► Colored de Bruijn graphs,extensions of the de Bruijn graphs are fundamental data structures for the analysis of high-throughput sequencing data. Although colored de Bruin graphs…
(more)
▼ Colored de Bruijn
graphs,extensions of the de Bruijn
graphs are fundamental data structures for the analysis of high-throughput sequencing data. Although colored de Bruin
graphs were designed for the detection of genetic variations among individuals of a population, they also can be helpful in disentangling the De Bruijn
graphs. One of the challenges of colored De Bruijn
graphs is lack of read coherence, meaning the correspondences between k-mers and reads are lost. Consequently, colored de Bruijn
graphs are prone to generating inaccurate contigs. Moreover, to be applicable to population-scale cohorts and to be able to dynamically add or remove samples to the study, it is essential to build and store colored de Bruijn
graphs in a space and time-efficient manner.
Advisors/Committee Members: Boucher,Christina A (committee chair), Sahni,Sartaj Kumar (committee member), Nelson,Corwin D (committee member).
Subjects/Keywords: coloredgraphs – graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Alipanahi Ramandi, B. (2020). Variants and Applications of Colored De Bruijn Graphs. (Doctoral Dissertation). University of Florida. Retrieved from https://ufdc.ufl.edu/UFE0056439
Chicago Manual of Style (16th Edition):
Alipanahi Ramandi, Bahareh. “Variants and Applications of Colored De Bruijn Graphs.” 2020. Doctoral Dissertation, University of Florida. Accessed April 21, 2021.
https://ufdc.ufl.edu/UFE0056439.
MLA Handbook (7th Edition):
Alipanahi Ramandi, Bahareh. “Variants and Applications of Colored De Bruijn Graphs.” 2020. Web. 21 Apr 2021.
Vancouver:
Alipanahi Ramandi B. Variants and Applications of Colored De Bruijn Graphs. [Internet] [Doctoral dissertation]. University of Florida; 2020. [cited 2021 Apr 21].
Available from: https://ufdc.ufl.edu/UFE0056439.
Council of Science Editors:
Alipanahi Ramandi B. Variants and Applications of Colored De Bruijn Graphs. [Doctoral Dissertation]. University of Florida; 2020. Available from: https://ufdc.ufl.edu/UFE0056439
University of Oxford
5.
Saller, Sophia.
Local limit theorem in random graphs and graphs on non-constant surfaces.
Degree: PhD, 2020, University of Oxford
URL: http://ora.ox.ac.uk/objects/uuid:147400e3-0a9b-46d1-b0c9-9acba7b94516
;
https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.813535
► The thesis is split into two parts. In the first part we prove a local limit theorem for the number of appearances of the complete…
(more)
▼ The thesis is split into two parts. In the first part we prove a local limit theorem for the number of appearances of the complete graph on four vertices, K4, in the Erdös-Rényi Random graph G(n, p) for p in (0, 1) a fixed constant. The proof of this is based on bounding the characteristic function of the number of K4 in G(n, p) by using different conditioning arguments for different ranges of t. The second part treats classes of graphs embeddable in either an orientable surface of Euler genus at most g(n), denoted by G^(g(n)), or non-orientable surface of Euler genus at most g(n), denoted by H^(g(n)), for different non-constant functions g(n). We first find bounds on the sizes of these classes and prove that as long as g(n) = o(n/log3(n)), the classes G^(g(n)) and H^(g(n)) both have a growth constant equal to the planar graph growth constant. As long as g(n) = O(n/log(n)) it is further shown that the classes Gg(n) and H^(g(n)) are both small. We then go on to show which properties graphs in these graph classes commonly display, such as giving bounds on the number of edges, faces, pendant vertices, the maximum degree and the probability of connectedness.
Subjects/Keywords: Random graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Saller, S. (2020). Local limit theorem in random graphs and graphs on non-constant surfaces. (Doctoral Dissertation). University of Oxford. Retrieved from http://ora.ox.ac.uk/objects/uuid:147400e3-0a9b-46d1-b0c9-9acba7b94516 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.813535
Chicago Manual of Style (16th Edition):
Saller, Sophia. “Local limit theorem in random graphs and graphs on non-constant surfaces.” 2020. Doctoral Dissertation, University of Oxford. Accessed April 21, 2021.
http://ora.ox.ac.uk/objects/uuid:147400e3-0a9b-46d1-b0c9-9acba7b94516 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.813535.
MLA Handbook (7th Edition):
Saller, Sophia. “Local limit theorem in random graphs and graphs on non-constant surfaces.” 2020. Web. 21 Apr 2021.
Vancouver:
Saller S. Local limit theorem in random graphs and graphs on non-constant surfaces. [Internet] [Doctoral dissertation]. University of Oxford; 2020. [cited 2021 Apr 21].
Available from: http://ora.ox.ac.uk/objects/uuid:147400e3-0a9b-46d1-b0c9-9acba7b94516 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.813535.
Council of Science Editors:
Saller S. Local limit theorem in random graphs and graphs on non-constant surfaces. [Doctoral Dissertation]. University of Oxford; 2020. Available from: http://ora.ox.ac.uk/objects/uuid:147400e3-0a9b-46d1-b0c9-9acba7b94516 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.813535
Rutgers University
6.
Baron, Jacob D., 1988-.
Two problems on cycles in random graphs.
Degree: PhD, Mathematics, 2016, Rutgers University
URL: https://rucore.libraries.rutgers.edu/rutgers-lib/51229/
► We prove three results. First, an old conjecture of Zs. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of…
(more)
▼ We prove three results. First, an old conjecture of Zs. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of a set of edges meeting all triangles to the maximum size, ν3(G), of an edge-disjoint triangle packing is at most 2. Disproving a conjecture of R. Yuster [40], we show that for any fixed, positive α there are arbitrarily large graphs G of positive density satisfying τ3(G) > (1 − o(1))|G|/2 and ν3(G) < (1 + α)|G|/4. Second, write C(G) for the cycle space of a graph G, Cκ(G) for the subspace of C(G) spanned by the copies of Cκ in G, Tκ for the class of graphs satisfying Cκ(G) = C(G), and Qκ for the class of graphs each of whose edges lies in a Cκ. We prove that for every odd κ ≥ 3 and G = Gn,p, max p Pr(G ∈ Qκ Tκ) → 0; so the Cκ’s of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [12]. Third, we extend the seminal van den Berg–Kesten Inequality [9] on disjoint occurrence of two events to a setting with arbitrarily many events, where the quantity of interest is the maximum number that occur disjointly. This provides a handy tool for bounding upper tail probabilities for event counts in a product probability space.
Advisors/Committee Members: Kahn, Jeff (chair), Komlos, Janos (internal member), Saks, Michael (internal member), Yuster, Raphael (outside member).
Subjects/Keywords: Random graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Baron, Jacob D., 1. (2016). Two problems on cycles in random graphs. (Doctoral Dissertation). Rutgers University. Retrieved from https://rucore.libraries.rutgers.edu/rutgers-lib/51229/
Chicago Manual of Style (16th Edition):
Baron, Jacob D., 1988-. “Two problems on cycles in random graphs.” 2016. Doctoral Dissertation, Rutgers University. Accessed April 21, 2021.
https://rucore.libraries.rutgers.edu/rutgers-lib/51229/.
MLA Handbook (7th Edition):
Baron, Jacob D., 1988-. “Two problems on cycles in random graphs.” 2016. Web. 21 Apr 2021.
Vancouver:
Baron, Jacob D. 1. Two problems on cycles in random graphs. [Internet] [Doctoral dissertation]. Rutgers University; 2016. [cited 2021 Apr 21].
Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/51229/.
Council of Science Editors:
Baron, Jacob D. 1. Two problems on cycles in random graphs. [Doctoral Dissertation]. Rutgers University; 2016. Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/51229/
Indian Institute of Science
7.
Francis, Mathew C.
Intersection Graphs Of Boxes And Cubes.
Degree: PhD, Faculty of Engineering, 2011, Indian Institute of Science
URL: http://etd.iisc.ac.in/handle/2005/1027
► A graph Gis said to be an intersection graph of sets from a family of sets if there exists a function ƒ : V(G)→ such…
(more)
▼ A graph Gis said to be an intersection graph of sets from a family of sets if there exists a function ƒ : V(G)→ such that for u,v V(G), (u,v) E(G) ƒ (u) ƒ (v) ≠ . Interval
graphs are thus the intersection
graphs of closed intervals on the real line and unit interval
graphs are the intersection
graphs of unit length intervals on the real line. An interval on the real line can be generalized to a “kbox” in Rk.A kbox B =(R1,R2,...,Rk), where each Riis a closed interval on the real line, is defined to be the Cartesian product R1x R2x…x Rk. If each Ri is a unit length interval, we call B a k-cube. Thus, 1-boxes are just closed intervals on the real line whereas 2-boxes are axis-parallel rectangles in the plane. We study the intersection
graphs of k-boxes and k-cubes. The parameter boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes. Thus, interval
graphs are the
graphs with boxicity at most 1 and unit interval
graphs are the
graphs with cubicity at most 1. These parameters were introduced by F. S.Roberts in 1969.
In some sense, the boxicity of a graph is a measure of how different a graph is from an interval graph and in a similar way, the cubicity is a measure of how different the graph is from a unit interval graph. We prove several upper bounds on the boxicity and cubicity of general as well as special classes of
graphs in terms of various graph parameters such as the maximum degree, the number of vertices and the bandwidth.
The following are some of the main results presented.
1. We show that for any graph G with maximum degree Δ , box(G)≤ Δ 22 . This result implies that bounded degree
graphs have bounded boxicity no matter how large the graph might be.
2. It was shown in [18] that the boxicity of a graph on n vertices with maximum degree Δ is O(Δ ln n). But a similar bound does not hold for the average degree davof a graph. [18] gives
graphs in which the boxicity is exponentially larger than davln n. We show that even though an O(davln n) upper bound for boxicity does not hold for all
graphs, for almost all
graphs, boxicity is O(davln n).
3. The ratio of the cubicity to boxicity of any graph shown in [15] when combined with the results on boxicity show that cub(G) is O(Δ ln 2 n) and O(2 ln n) for any graph G on n vertices and with maximum degree . By using a randomized construction, we prove the better upper bound cub(G) ≤ [4(Δ + 1) ln n.]
4. Two results relating the cubicity of a graph to its bandwidth b are presented. First, it is shown that cub(G) ≤ 12(Δ + 1)[ ln(2b)] + 1. Next, we derive the upper bound cub(G) ≤ b + 1. This bound is used to derive new upper bounds on the cubicity of special graph classes like circular arc
graphs, cocomparability
graphs and ATfree
graphs in relation to the maximum degree.
5. The upper bound for cubicity in terms of the bandwidth gives an upper bound of Δ + 1 for the…
Advisors/Committee Members: Chandran, L Sunil (advisor).
Subjects/Keywords: Computer Graphics; Boxicity (Graphs); Cubicity (Graphs); Interval Graphs; Halin Graphs; Planar Graphs; Intersection Graphs; Random Graphs; Computer Science
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Francis, M. C. (2011). Intersection Graphs Of Boxes And Cubes. (Doctoral Dissertation). Indian Institute of Science. Retrieved from http://etd.iisc.ac.in/handle/2005/1027
Chicago Manual of Style (16th Edition):
Francis, Mathew C. “Intersection Graphs Of Boxes And Cubes.” 2011. Doctoral Dissertation, Indian Institute of Science. Accessed April 21, 2021.
http://etd.iisc.ac.in/handle/2005/1027.
MLA Handbook (7th Edition):
Francis, Mathew C. “Intersection Graphs Of Boxes And Cubes.” 2011. Web. 21 Apr 2021.
Vancouver:
Francis MC. Intersection Graphs Of Boxes And Cubes. [Internet] [Doctoral dissertation]. Indian Institute of Science; 2011. [cited 2021 Apr 21].
Available from: http://etd.iisc.ac.in/handle/2005/1027.
Council of Science Editors:
Francis MC. Intersection Graphs Of Boxes And Cubes. [Doctoral Dissertation]. Indian Institute of Science; 2011. Available from: http://etd.iisc.ac.in/handle/2005/1027
University of Georgia
8.
Rath, Bijaya.
Generation of non-isomorphic cubic Cayley graphs.
Degree: 2014, University of Georgia
URL: http://hdl.handle.net/10724/26988
► This thesis investigates the generation of non-isomorphic simple cubic Cayley graphs. The research is motivated indirectly by the long standing conjecture that all Cayley graphs…
(more)
▼ This thesis investigates the generation of non-isomorphic simple cubic Cayley graphs. The research is motivated indirectly by the long standing conjecture that all Cayley graphs with at least three vertices are Hamiltonian. All simple cubic
Cayley graphs of degree <= 7 were generated. By a simple Cayley graph is meant one for which the underlying Cayley digraph is symmetric and irreflexive. Put another way, each generator is an involution which is not the identity. Results are presented
which show which pairs of non-conjugate triples of generators, up to degree 7, yield isomorphic Cayley graphs. These Cayley graphs range in size up to 5040, and include a number for which hamiltonicity or non-hamiltonicity has not been determined. In
addition to the census results some sufficient (but by no means necessary) conditions are shown for isomorphism between Cayley graphs, and an efficient method of counting non-conjugate triples of involutions is developed.
Subjects/Keywords: Cayley graphs; Hamiltonian graphs; graph isomorphism
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Rath, B. (2014). Generation of non-isomorphic cubic Cayley graphs. (Thesis). University of Georgia. Retrieved from http://hdl.handle.net/10724/26988
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Rath, Bijaya. “Generation of non-isomorphic cubic Cayley graphs.” 2014. Thesis, University of Georgia. Accessed April 21, 2021.
http://hdl.handle.net/10724/26988.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Rath, Bijaya. “Generation of non-isomorphic cubic Cayley graphs.” 2014. Web. 21 Apr 2021.
Vancouver:
Rath B. Generation of non-isomorphic cubic Cayley graphs. [Internet] [Thesis]. University of Georgia; 2014. [cited 2021 Apr 21].
Available from: http://hdl.handle.net/10724/26988.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Rath B. Generation of non-isomorphic cubic Cayley graphs. [Thesis]. University of Georgia; 2014. Available from: http://hdl.handle.net/10724/26988
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Jawaharlal Nehru University
9.
Krishna Reddy, Polepalli.
Synchronization based on data flow graphs for distributed
and replicated databases; -.
Degree: Computer Science, 1993, Jawaharlal Nehru University
URL: http://shodhganga.inflibnet.ac.in/handle/10603/16640
► In this study, we present concurrency control algorithms based on data flow graphs for newlinedistributed and replicated databases. newlineGraphical representations such as token models and…
(more)
▼ In this study, we present concurrency control
algorithms based on data flow graphs for newlinedistributed and
replicated databases. newlineGraphical representations such as
token models and structure models are widely applied newlineto
represent data flow programs. Data flow programs are represented by
directed graphs called newlinedata flow graphs where nodes
represent the operations to be performed and arcs represent
newlinethe data dependencies between them. The scheduling of
operations is constrained by the data newlinedependencies
identified by the graph. So, data flow scheduling mechanism could
execute newlineoperations based upon the dependency constraints
defined by the data flow graph. In this newlineway, concurrency is
achieved through graphs. newlineIn this study we explore t~~ use of
data flow graphs to design concurrency control newlinealgorithms.
Precedence graphs are often used to determine serializability, and
wait-for-graphs newlineare often used to detect deadlocks. Among
these, acyclic precedence graphs indicate newlineserializability,
and acyclic wait-for-graphs imply freedom from deadlocks. The tools
for newlineserializability theory, and transaction management
coupled with data flow graphs will provide newlinesolutions that
are more efficient than conventional concurrency control
techniques, such as, newlinetwo-phase locking. In the same light,
we apply data flow graphs for concurrency control for
newlinedistributed, and replicated databases. newlineAt first, we
propose a concurrency control algorithm based on data flow graphs
for a newlinedistributed database system. The concurrency control
approaches based on locking, require newlineadditional efforts in
deadlock detection and its elimination. The deadlock resolution
protocols newlineassociated with deadlock detection algorithms
abort (restart) some transactions in the deadlock newlinecycle. The
restarted transaction must release all its locks and send out the
requests again. The newlinepossibility of a deadlock is also
connected to existence of unpredictable delays and repeated
newlinerestarts of transactions in a deadlock
cycle.
Appendix p.134-143, Bibilography p.164,
Abbrevations, Graphs
Advisors/Committee Members: Bharadwaj, K K, Bhalla, Subhash.
Subjects/Keywords: Computer Science; graphs; Replicated; databses; flow graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Krishna Reddy, P. (1993). Synchronization based on data flow graphs for distributed
and replicated databases; -. (Thesis). Jawaharlal Nehru University. Retrieved from http://shodhganga.inflibnet.ac.in/handle/10603/16640
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Krishna Reddy, Polepalli. “Synchronization based on data flow graphs for distributed
and replicated databases; -.” 1993. Thesis, Jawaharlal Nehru University. Accessed April 21, 2021.
http://shodhganga.inflibnet.ac.in/handle/10603/16640.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Krishna Reddy, Polepalli. “Synchronization based on data flow graphs for distributed
and replicated databases; -.” 1993. Web. 21 Apr 2021.
Vancouver:
Krishna Reddy P. Synchronization based on data flow graphs for distributed
and replicated databases; -. [Internet] [Thesis]. Jawaharlal Nehru University; 1993. [cited 2021 Apr 21].
Available from: http://shodhganga.inflibnet.ac.in/handle/10603/16640.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Krishna Reddy P. Synchronization based on data flow graphs for distributed
and replicated databases; -. [Thesis]. Jawaharlal Nehru University; 1993. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/16640
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Iowa State University
10.
Blumenthal, Adam.
Domination problems in directed graphs and inducibility of nets.
Degree: 2020, Iowa State University
URL: https://lib.dr.iastate.edu/etd/17952
► In this thesis we discuss two topics: domination parameters and inducibility. In the first chapter, we introduce basic concepts, definitions, and a brief history for…
(more)
▼ In this thesis we discuss two topics: domination parameters and inducibility. In the first chapter, we introduce basic concepts, definitions, and a brief history for both types of problems. We will first inspect domination parameters in graphs, particularly independent domination in regular graphs and we answer a question of Goddard and Henning. Additionally, we provide some constructions for graphs regular graphs of small degree to provide lower bounds on the independent domination ratio of these classes of graphs. In Chapter 3 we expand our exploration of independent domination into the realm of directed graphs. We will prove several results including providing a fastest known algorithm for determining existence of an independent dominating set in directed graphs with minimum in degree at least one and period not eqeual to one. We also construct a set of counterexamples to the analogue of Vizing's Conjecture for this setting. In the fourth chapter, we pivot from independent domination to split domination in directed graphs, where we introduce the split domination sequence. We will determine that almost all possible split domination sequences are realizable by some graphs, and state several open questions that would be of interest to continue on this field. In the fifth chapter we will provide a brief introduction to Flag Algebras, then determine the unique maximizer of induced net graphs in graphs of certain orders.
Subjects/Keywords: Directed Graphs; Domination; Extremal Combinatorics; Graphs; Inducibility
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Blumenthal, A. (2020). Domination problems in directed graphs and inducibility of nets. (Thesis). Iowa State University. Retrieved from https://lib.dr.iastate.edu/etd/17952
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Blumenthal, Adam. “Domination problems in directed graphs and inducibility of nets.” 2020. Thesis, Iowa State University. Accessed April 21, 2021.
https://lib.dr.iastate.edu/etd/17952.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Blumenthal, Adam. “Domination problems in directed graphs and inducibility of nets.” 2020. Web. 21 Apr 2021.
Vancouver:
Blumenthal A. Domination problems in directed graphs and inducibility of nets. [Internet] [Thesis]. Iowa State University; 2020. [cited 2021 Apr 21].
Available from: https://lib.dr.iastate.edu/etd/17952.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Blumenthal A. Domination problems in directed graphs and inducibility of nets. [Thesis]. Iowa State University; 2020. Available from: https://lib.dr.iastate.edu/etd/17952
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Louisiana State University
11.
Iverson, Perry K.
Refining the characterization of projective graphs.
Degree: PhD, Applied Mathematics, 2013, Louisiana State University
URL: etd-07072013-161459
;
https://digitalcommons.lsu.edu/gradschool_dissertations/3914
► Archdeacon showed that the class of graphs embeddable in the projective plane is characterized by a set of 35 excluded minors. Robertson, Seymour and Thomas…
(more)
▼ Archdeacon showed that the class of graphs embeddable in the projective plane is characterized by a set of 35 excluded minors. Robertson, Seymour and Thomas in an unpublished result found the excluded minors for the class of k-connected graphs embeddable on the projective plane for k = 1,2,3. We give a short proof of that result and then determine the excluded minors for the class of internally 4-connected projective graphs. Hall showed that a 3-connected graph diff_x000B_erent from K5 is planar if and only if it has K3,3 as a minor. We provide two analogous results for projective graphs. For any minor-closed class of graphs C, we say that a set of k-connected graphs E disjoint from C is a k-connected excludable set for C if all but a _x000C_finite number of k-connected graphs not in C have a minor in E. Hall's result is equivalent to saying that {K3,3} is a 3-connected excludable set for the class of planar graphs. We classify all minimal 3-connected excludable sets and fi_x000C_nd one minimal internally 4-connected excludable set for the class of projective graphs. In doing so, we also prove strong splitter theorems for 3-connected and internally 4-connected graphs that could have application to other problems of this type.
Subjects/Keywords: minors; excluded minors; projective graphs; graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Iverson, P. K. (2013). Refining the characterization of projective graphs. (Doctoral Dissertation). Louisiana State University. Retrieved from etd-07072013-161459 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3914
Chicago Manual of Style (16th Edition):
Iverson, Perry K. “Refining the characterization of projective graphs.” 2013. Doctoral Dissertation, Louisiana State University. Accessed April 21, 2021.
etd-07072013-161459 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3914.
MLA Handbook (7th Edition):
Iverson, Perry K. “Refining the characterization of projective graphs.” 2013. Web. 21 Apr 2021.
Vancouver:
Iverson PK. Refining the characterization of projective graphs. [Internet] [Doctoral dissertation]. Louisiana State University; 2013. [cited 2021 Apr 21].
Available from: etd-07072013-161459 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3914.
Council of Science Editors:
Iverson PK. Refining the characterization of projective graphs. [Doctoral Dissertation]. Louisiana State University; 2013. Available from: etd-07072013-161459 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3914
Louisiana State University
12.
Dziobiak, Stanislaw.
Excluded-minor characterization of apex-outerplanar graphs.
Degree: PhD, Applied Mathematics, 2011, Louisiana State University
URL: etd-07062011-183918
;
https://digitalcommons.lsu.edu/gradschool_dissertations/3102
► It is well known that the class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: K4 and K2,3. The class…
(more)
▼ It is well known that the class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: K4 and K2,3. The class of graphs that contain a vertex whose removal leaves an outerplanar graph is also minor-closed. We provide the complete list of 57 excluded minors for this class.
Subjects/Keywords: outerplanar graphs; excluded minors; minors; graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Dziobiak, S. (2011). Excluded-minor characterization of apex-outerplanar graphs. (Doctoral Dissertation). Louisiana State University. Retrieved from etd-07062011-183918 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3102
Chicago Manual of Style (16th Edition):
Dziobiak, Stanislaw. “Excluded-minor characterization of apex-outerplanar graphs.” 2011. Doctoral Dissertation, Louisiana State University. Accessed April 21, 2021.
etd-07062011-183918 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3102.
MLA Handbook (7th Edition):
Dziobiak, Stanislaw. “Excluded-minor characterization of apex-outerplanar graphs.” 2011. Web. 21 Apr 2021.
Vancouver:
Dziobiak S. Excluded-minor characterization of apex-outerplanar graphs. [Internet] [Doctoral dissertation]. Louisiana State University; 2011. [cited 2021 Apr 21].
Available from: etd-07062011-183918 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3102.
Council of Science Editors:
Dziobiak S. Excluded-minor characterization of apex-outerplanar graphs. [Doctoral Dissertation]. Louisiana State University; 2011. Available from: etd-07062011-183918 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3102
University of Waterloo
13.
Lato, Sabrina.
Quantum Walks on Oriented Graphs.
Degree: 2019, University of Waterloo
URL: http://hdl.handle.net/10012/14338
► This thesis extends results about periodicity and perfect state transfer to oriented graphs. We prove that if a vertex a is periodic, then elements of…
(more)
▼ This thesis extends results about periodicity and perfect state transfer
to oriented graphs. We prove that if a vertex a is periodic, then elements of
the eigenvalue support lie in Z √∆ for some squarefree negative integer
∆. We find an infinite family of orientations of the complete graph that are
periodic. We find an example of a graph with both perfect state transfer
and periodicity that is not periodic at an integer multiple of the period, and
we prove and use Gelfond-Schneider Theorem to show that every oriented
graph with perfect state transfer between two vertices will have both vertices
periodic. We find a complete characterization of when perfect state transfer
can occur in oriented graphs, and find a new example of a graph where one
vertex has perfect state transfer to multiple other vertices.
Subjects/Keywords: quantum walks; graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Lato, S. (2019). Quantum Walks on Oriented Graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/14338
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Lato, Sabrina. “Quantum Walks on Oriented Graphs.” 2019. Thesis, University of Waterloo. Accessed April 21, 2021.
http://hdl.handle.net/10012/14338.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Lato, Sabrina. “Quantum Walks on Oriented Graphs.” 2019. Web. 21 Apr 2021.
Vancouver:
Lato S. Quantum Walks on Oriented Graphs. [Internet] [Thesis]. University of Waterloo; 2019. [cited 2021 Apr 21].
Available from: http://hdl.handle.net/10012/14338.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Lato S. Quantum Walks on Oriented Graphs. [Thesis]. University of Waterloo; 2019. Available from: http://hdl.handle.net/10012/14338
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Newcastle
14.
Feria Puron, Ramiro.
Large interconnection networks with given degree and diameter.
Degree: PhD, 2015, University of Newcastle
URL: http://hdl.handle.net/1959.13/1295870
► Research Doctorate - Doctor of Philosophy (PhD)
This thesis investigates and provides several answers for one of the most representative open problems in the design…
(more)
▼ Research Doctorate - Doctor of Philosophy (PhD)
This thesis investigates and provides several answers for one of the most representative open problems in the design of interconnection networks. In the last few decades, the ability to design interconnection networks satisfying practical requirements and constraints has become a topic of major interest. In most circumstances, however, this has turned out to be a rather challenging task, leading to questions that have become the source of more than one interesting unsolved problem. One of these problems that has received significant attention deals with the design of networks as large as possible in terms of the number of nodes, given a limit on the number of connections attached to a node and a limit on the distance between any two nodes of the network. When translated to graph-theoretical terms this leads to the Degree/Diameter Problem, which asks for the largest number of vertices in a graph (and the graph itself) with a given maximum degree and diameter. The Degree/Diameter problem has been investigated since it was stated in 1964, yet is has endured as an open problem for more than fifty years now. A generous number of partial outcomes have been obtained to date, without narrowing the considerable gap remaining between the currently known upper and lower bounds for most degrees and diameters. The networks in question may be subject to further classification, such as being planar or bipartite, which restricts the Degree/Diameter Problem to the class of graphs under consideration. In this thesis we make substantial contributions to the Degree/Diameter Problem by providing improvements in the two traditional research directions: lowering the upper bounds for by proving the non-existence of graphs, and increasing the lower bounds by finding or giving constructions of ever larger graphs with given degree and diameter. The methodology used relies on a mixture of combinatorial approaches, graph compounding techniques, as well as algorithmic techniques and computer search. Our outcomes cover four of the most prominent classes of graphs studied: general graphs, bipartite graphs, circulant graphs, and graphs embeddable on surfaces. Among others, we obtain the following results: For the class of bipartite graphs, we use combinatorial approaches to improve the current upper bounds for more than two thirds of all possible combinations of degree and diameter. In a partially computer assisted proof, we prove that the largest known bipartite graph of degree 7 and diameter 3 is optimal. We also find by computer search a bipartite graph of degree 11 and diameter 3, thus improving the former lower bound by 4 vertices. ; For the class of general graphs, we use a similar strategy to improve the current upper bounds for more than one half of all possible combinations of degree and diameter. ; For the class of circulant graphs, we design and implement an efficient algorithm to find circulant graphs of small diameter. We find 15 largest known circulant graphs, with diameters ranging…
Advisors/Committee Members: University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science.
Subjects/Keywords: degree diameter problem; graphs; moore bound; bipartite graphs; circulant graphs; graphs on surfaces
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Feria Puron, R. (2015). Large interconnection networks with given degree and diameter. (Doctoral Dissertation). University of Newcastle. Retrieved from http://hdl.handle.net/1959.13/1295870
Chicago Manual of Style (16th Edition):
Feria Puron, Ramiro. “Large interconnection networks with given degree and diameter.” 2015. Doctoral Dissertation, University of Newcastle. Accessed April 21, 2021.
http://hdl.handle.net/1959.13/1295870.
MLA Handbook (7th Edition):
Feria Puron, Ramiro. “Large interconnection networks with given degree and diameter.” 2015. Web. 21 Apr 2021.
Vancouver:
Feria Puron R. Large interconnection networks with given degree and diameter. [Internet] [Doctoral dissertation]. University of Newcastle; 2015. [cited 2021 Apr 21].
Available from: http://hdl.handle.net/1959.13/1295870.
Council of Science Editors:
Feria Puron R. Large interconnection networks with given degree and diameter. [Doctoral Dissertation]. University of Newcastle; 2015. Available from: http://hdl.handle.net/1959.13/1295870
Victoria University of Wellington
15.
Snook, Michael.
Matroids, Complexity and Computation.
Degree: 2013, Victoria University of Wellington
URL: http://hdl.handle.net/10063/2885
► The node deletion problem on graphs is: given a graph and integer k, can we delete no more than k vertices to obtain a graph…
(more)
▼ The node deletion problem on
graphs is: given a graph and integer k, can we
delete no more than k vertices to obtain a graph that satisfies some property π.
Yannakakis showed that this problem is NP-complete for an infinite family of well-
defined properties. The edge deletion problem and matroid deletion problem are
similar problems where given a graph or matroid respectively, we are asked if we
can delete no more than k edges/elements to obtain a graph/matroid that satisfies
a property π. We show that these problems are NP-hard for similar well-defined
infinite families of properties.
In 1991 Vertigan showed that it isP-complete to count the number of bases
of a representable matroid over any fixed field. However no publication has been
produced. We consider this problem and show that it is #P-complete to count
the number of bases of matroids representable over any infinite fixed field or finite
fields of a fixed characteristic.
There are many different ways of describing a matroid. Not all of these are
polynomially equivalent. That is, given one description of a matroid, we cannot
create another description for the same matroid in time polynomial in the size of
the first description. Due to this, the complexity of matroid problems can vary
greatly depending on the method of description used. Given one description a
problem might be in P while another description gives an NP-complete problem.
Based on these interactions between descriptions, we create and study the hierarchy
of all matroid descriptions and generalize this to all descriptions of countable
objects.
Advisors/Committee Members: Mayhew, Dillon, Whittle, Geoff.
Subjects/Keywords: Graphs; Computation; Complexity
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Snook, M. (2013). Matroids, Complexity and Computation. (Doctoral Dissertation). Victoria University of Wellington. Retrieved from http://hdl.handle.net/10063/2885
Chicago Manual of Style (16th Edition):
Snook, Michael. “Matroids, Complexity and Computation.” 2013. Doctoral Dissertation, Victoria University of Wellington. Accessed April 21, 2021.
http://hdl.handle.net/10063/2885.
MLA Handbook (7th Edition):
Snook, Michael. “Matroids, Complexity and Computation.” 2013. Web. 21 Apr 2021.
Vancouver:
Snook M. Matroids, Complexity and Computation. [Internet] [Doctoral dissertation]. Victoria University of Wellington; 2013. [cited 2021 Apr 21].
Available from: http://hdl.handle.net/10063/2885.
Council of Science Editors:
Snook M. Matroids, Complexity and Computation. [Doctoral Dissertation]. Victoria University of Wellington; 2013. Available from: http://hdl.handle.net/10063/2885
16.
El Harabi, Rafika.
Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes.
Degree: Docteur es, Automatique, Génie informatique, Traitement du Signal et Images, 2011, Université Lille I – Sciences et Technologies
URL: http://www.theses.fr/2011LIL10074
► Le travail de thèse proposé concerne la conception intégrée des algorithmes de surveillance des processus chimiques à base de modèles bond graph. Cette recherche est…
(more)
▼ Le travail de thèse proposé concerne la conception intégrée des algorithmes de surveillance des processus chimiques à base de modèles bond graph. Cette recherche est réalisée dans le cadre de la thématique «Bond graphs pour la supervision des procédés énergétiques» développée entre l’Université de Gabés (Tunisie) et l’Ecole Polytechnique Universitaire de Lille (France). Les processus chimiques sont des procédés polluants et à risque. Ils nécessitent alors pour la protection de l’environnement et du personnel des systèmes de surveillance en ligne pour la détection précoce et l’identification des défaillances. Un processus chimique est le siège de phénomènes de nature diverse : chimiques et ou biochimiques, thermo-fluidique, …. Leur modélisation nécessite alors une approche unifiée. L’outil bond graph par son caractère multidisciplinaire est bien adapté à cette tâche. D’autre part, cet outil peut aussi être utilisé pour la conception d’algorithmes de diagnostic grâce à ses propriétés comportementales, causales et structurelles et déterminer ainsi les conditions de surveillabilité structurelle des équipements pertinents sans calcul numérique. Les principales scientifiques contributions peuvent être résumées comme suit : (i) élaboration d’une bibliothèque de modèles Bond Graph de composants et phénomènes chimiques (ii) méthodologie de diagnostic à base de bond graphs pour la génération d’indicateurs de fautes sensibles à l’apparition des réactions secondaires sources de pollution et d’explosion, (iii) diagnostic robuste aux incertitudes paramétriques du modèle Bond Graphs couplés, (iv) informatisation des procédures d’analyse de surveillabilité d’une classe de procédés chimiques, (v) application à un procédé réel (installation d’estérification).
The proposed Ph.D. thesis deals with integrated design of bond graph model based for health monitoring of chemical processes. This research work is performed within the framework of the topic “Bond graphs for supervision of energetic processes" developed between the University of Gabés (Tunisia) and “Polytech’Lille”, the Engineering School within the University of Science and Technology of Lille. The chemical processes are polluting processes and with risk. They need, for staff safety and environmental protection, online surveillance for early detection and the identification of the failures. chemical processes occur phenomena of various nature: chemical and or biochemical, thermo-fluidic… Their modeling requires a unified approach. The Bond graph as a multidisciplinary tool is well suited to this task.Furthermore, this tool can be used also for the design of diagnosis algorithms thanks to its behavioral, causal and structural properties, and allows providing structural diagnosability conditions of the pertinent equipment without numerical calculation. The main scientific contributions of this research can be summarized as follows: (i)elaboration of a data base of dynamic bond graph models of components and chemical phenomena, (ii) methodology of bond graph model based…
Advisors/Committee Members: Ould Bouamama, Belkacem (thesis director), Abdelkrim, Mohamed Naceur (thesis director).
Subjects/Keywords: Bond Graphs; 629.895
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
El Harabi, R. (2011). Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes. (Doctoral Dissertation). Université Lille I – Sciences et Technologies. Retrieved from http://www.theses.fr/2011LIL10074
Chicago Manual of Style (16th Edition):
El Harabi, Rafika. “Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes.” 2011. Doctoral Dissertation, Université Lille I – Sciences et Technologies. Accessed April 21, 2021.
http://www.theses.fr/2011LIL10074.
MLA Handbook (7th Edition):
El Harabi, Rafika. “Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes.” 2011. Web. 21 Apr 2021.
Vancouver:
El Harabi R. Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes. [Internet] [Doctoral dissertation]. Université Lille I – Sciences et Technologies; 2011. [cited 2021 Apr 21].
Available from: http://www.theses.fr/2011LIL10074.
Council of Science Editors:
El Harabi R. Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes. [Doctoral Dissertation]. Université Lille I – Sciences et Technologies; 2011. Available from: http://www.theses.fr/2011LIL10074
University of Victoria
17.
Neilson, Linda.
Broadcast independence in graphs.
Degree: Department of Mathematics and Statistics, 2019, University of Victoria
URL: http://hdl.handle.net/1828/11084
► The usual graph parameters related to independent and dominating sets can be adapted to broadcasts on graphs. We examine some possible definitions for an inde-…
(more)
▼ The usual graph parameters related to independent and dominating sets can be adapted to broadcasts on
graphs. We examine some possible definitions for an inde- pendent broadcast. We determine the minimum maximal and the maximum broad- cast weight for all our independence parameters on both paths and grids. For
graphs in general, we examine the relationships between these broadcast independence pa- rameters and the existing minimum and maximum minimal broadcast domination weight (or cost). We also determine upper and lower bounds for maximum boundary independent broadcasts and a new upper bound for hearing independent broadcasts.
Advisors/Committee Members: Mynhardt, C. M. (supervisor).
Subjects/Keywords: Broadcasts; Graphs; Independence
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Neilson, L. (2019). Broadcast independence in graphs. (Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/11084
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Neilson, Linda. “Broadcast independence in graphs.” 2019. Thesis, University of Victoria. Accessed April 21, 2021.
http://hdl.handle.net/1828/11084.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Neilson, Linda. “Broadcast independence in graphs.” 2019. Web. 21 Apr 2021.
Vancouver:
Neilson L. Broadcast independence in graphs. [Internet] [Thesis]. University of Victoria; 2019. [cited 2021 Apr 21].
Available from: http://hdl.handle.net/1828/11084.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Neilson L. Broadcast independence in graphs. [Thesis]. University of Victoria; 2019. Available from: http://hdl.handle.net/1828/11084
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Victoria
18.
Hassanlou, Nasrin.
Probabilistic graph summarization.
Degree: Dept. of Computer Science, 2013, University of Victoria
URL: http://hdl.handle.net/1828/4403
► We study group-summarization of probabilistic graphs that naturally arise in social networks, semistructured data, and other applications. Our proposed framework groups the nodes and edges…
(more)
▼ We study group-summarization of probabilistic
graphs that naturally arise in social
networks, semistructured data, and other applications. Our proposed framework
groups the nodes and edges of the graph based on a user selected set of node attributes.
We present methods to compute useful graph aggregates without the need
to create all of the possible graph-instances of the original probabilistic graph. Also,
we present an algorithm for graph summarization based on pure relational (SQL)
technology. We analyze our algorithm and practically evaluate its efficiency using
an extended Epinions dataset as well as synthetic datasets. The experimental results
show the scalability of our algorithm and its efficiency in producing highly compressed
summary
graphs in reasonable time.
Advisors/Committee Members: Thomo, Alex (supervisor).
Subjects/Keywords: graphs; users; algorithms
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Hassanlou, N. (2013). Probabilistic graph summarization. (Masters Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/4403
Chicago Manual of Style (16th Edition):
Hassanlou, Nasrin. “Probabilistic graph summarization.” 2013. Masters Thesis, University of Victoria. Accessed April 21, 2021.
http://hdl.handle.net/1828/4403.
MLA Handbook (7th Edition):
Hassanlou, Nasrin. “Probabilistic graph summarization.” 2013. Web. 21 Apr 2021.
Vancouver:
Hassanlou N. Probabilistic graph summarization. [Internet] [Masters thesis]. University of Victoria; 2013. [cited 2021 Apr 21].
Available from: http://hdl.handle.net/1828/4403.
Council of Science Editors:
Hassanlou N. Probabilistic graph summarization. [Masters Thesis]. University of Victoria; 2013. Available from: http://hdl.handle.net/1828/4403
University of Florida
19.
Rodriguez, Miguel.
Reasoning over Multi-Source and Dynamic Knowledge Graphs.
Degree: PhD, Computer Engineering - Computer and Information Science and Engineering, 2019, University of Florida
URL: https://ufdc.ufl.edu/UFE0056138
► Innovative approaches to Information Extraction (IE) have enabled the creation of large Knowledge Graphs (KGs) (e.g., YAGO, NELL, DBPedia, Wikidata) and Dynamic Knowledge Graphs (e.g.,…
(more)
▼ Innovative approaches to Information Extraction (IE) have enabled the creation of large Knowledge
Graphs (KGs) (e.g., YAGO, NELL, DBPedia, Wikidata) and Dynamic Knowledge
Graphs (e.g., ICEWS, GDELT). These knowledge
graphs have become an increasingly popular domain knowledge representation used in semantic search, recommendation systems, question-answering, natural language processing, etc.
Advisors/Committee Members: Wang,Zhe (committee chair), Dobra,Alin Viorel (committee member), Raup-Krieger,Janice (committee member).
Subjects/Keywords: fusion – graphs – sequence
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Rodriguez, M. (2019). Reasoning over Multi-Source and Dynamic Knowledge Graphs. (Doctoral Dissertation). University of Florida. Retrieved from https://ufdc.ufl.edu/UFE0056138
Chicago Manual of Style (16th Edition):
Rodriguez, Miguel. “Reasoning over Multi-Source and Dynamic Knowledge Graphs.” 2019. Doctoral Dissertation, University of Florida. Accessed April 21, 2021.
https://ufdc.ufl.edu/UFE0056138.
MLA Handbook (7th Edition):
Rodriguez, Miguel. “Reasoning over Multi-Source and Dynamic Knowledge Graphs.” 2019. Web. 21 Apr 2021.
Vancouver:
Rodriguez M. Reasoning over Multi-Source and Dynamic Knowledge Graphs. [Internet] [Doctoral dissertation]. University of Florida; 2019. [cited 2021 Apr 21].
Available from: https://ufdc.ufl.edu/UFE0056138.
Council of Science Editors:
Rodriguez M. Reasoning over Multi-Source and Dynamic Knowledge Graphs. [Doctoral Dissertation]. University of Florida; 2019. Available from: https://ufdc.ufl.edu/UFE0056138
The Ohio State University
20.
Poole, Daniel James.
A Study of Random Hypergraphs and Directed Graphs.
Degree: PhD, Mathematics, 2014, The Ohio State University
URL: http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674
► We establish and describe the likely structure of random hypergraph and directed graph models, expanding upon classical results that pertain to the likely structure of…
(more)
▼ We establish and describe the likely structure of
random hypergraph and directed graph models, expanding upon
classical results that pertain to the likely structure of the
random undirected graph models. The random
<i>d</i>-uniform hypergraph process, begins as an empty
hypergraph on <i>n</i> vertices. At each step, a new
hyperedge of cardinality <i>d</i> is added; each new
hyperedge is chosen uniformly at random among all non-present
hyperedges. We prove a hypergraphic analogue of the
Bollobás-Thomason Theorem: for each fixed <i>k</i>,
with high probability, the stopping time for the hypergraph process
having minimum degree at least <i>k</i> coincides with
the stopping time for the process being
<i>k</i>-connected. Also, the diameter at the moment of
connectivity is shown to be one of at most nine deterministic
values near <i>ln n/ln((d-1)ln n)</i>. Finally, the
sharp threshold of existence of a weak (Berge) Hamilton cycle is
established.We study the random directed graph model <i>D(n,
m=cn)</i>, a random instance of a directed graph on
<i>n</i> vertices with <i>m</i> arcs. Karp
and Luczak independently found that for <i>c>1</i>,
with high probability, there is a unique strong component with size
linear in <i>n</i>. We prove that the pair of the
numbers of the vertices and arcs in the largest strong component,
once properly centered and scaled, is asymptotically Gaussian
distributed.
Advisors/Committee Members: Kahle, Matthew (Advisor), Pittel, Boris (Advisor).
Subjects/Keywords: Mathematics; Random Graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Poole, D. J. (2014). A Study of Random Hypergraphs and Directed Graphs. (Doctoral Dissertation). The Ohio State University. Retrieved from http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674
Chicago Manual of Style (16th Edition):
Poole, Daniel James. “A Study of Random Hypergraphs and Directed Graphs.” 2014. Doctoral Dissertation, The Ohio State University. Accessed April 21, 2021.
http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674.
MLA Handbook (7th Edition):
Poole, Daniel James. “A Study of Random Hypergraphs and Directed Graphs.” 2014. Web. 21 Apr 2021.
Vancouver:
Poole DJ. A Study of Random Hypergraphs and Directed Graphs. [Internet] [Doctoral dissertation]. The Ohio State University; 2014. [cited 2021 Apr 21].
Available from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674.
Council of Science Editors:
Poole DJ. A Study of Random Hypergraphs and Directed Graphs. [Doctoral Dissertation]. The Ohio State University; 2014. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674
Western Michigan University
21.
Byers, Alexis D.
Graceful Colorings and Connection in Graphs.
Degree: PhD, Mathematics, 2018, Western Michigan University
URL: https://scholarworks.wmich.edu/dissertations/3308
► For a graph G of size m, a graceful labeling of G is an injective function f : V (G) → {0, 1, .…
(more)
▼ For a graph
G of size
m, a graceful labeling of
G is an injective function
f :
V (
G)
→ {0
, 1
, . . . , m} that gives rise to a bijective function
f <em>
1</em>
:
E(
G)
→ {1
, 2
, . . . , m} defined by
f <em>
1</em>(
uv) =
|f (
u)
− f (
v)
|. A graph is graceful if it has a graceful labeling. Over the years, a number of variations of graceful labelings have been introduced, some of which have been described in terms of colorings.
A proper (vertex) coloring of a graph
G is an assignment of colors to the vertices of
G such that adjacent vertices are assigned distinct colors. The minimum number of colors required of a proper vertex coloring of
G is its chromatic number,
χ(
G). Similarly, a proper edge coloring of a graph
G is an assignment of colors to the edges of
G such that adjacent edges are assigned distinct colors. The minimum number of colors required of a proper edge coloring of
G is its chromatic index,
χ<em>
l</em>(
G).
A proper vertex coloring
c :
V (
G) → {1
, 2
, . . . , k} is called a graceful
k-coloring if the induced edge coloring
c<em>
l</em>
defined by
c<em>
l</em>(
uv) = |
c(
u) −
c(
v)| is also proper. The minimum positive integer
k for which
G has a graceful
k-coloring is its graceful chromatic number
χ<em>
g</em>(
G). These chromatic numbers are determined for several well-known classes of
graphs, including cycles, wheels and caterpillars. An upper bound for the graceful chromatic number of trees is determined in terms of its maximum degree. We also present several other results and conjectures on this coloring concept.
A graph is edge-colored if each of its edges is assigned a color (where adjacent edges may be assigned the same color). Let
G be an edge-colored connected graph. A path
P in an edge-colored graph
G is a rainbow path of
G if no two edges of
P are colored the same. An edge coloring
c of a connected graph
G is a rainbow coloring of
G if every pair of distinct vertices of
G are connected by a rainbow path in
G. In this case,
G is rainbow-connected. The minimum number of colors needed for a rainbow coloring of
G is referred to as the rainbow…
Advisors/Committee Members: Dr. Ping Zhang, Dr. Gary Chartrand, Dr. Clifton Ealy.
Subjects/Keywords: Graphs; coloring in graphs; connections in graphs; mathematics; Mathematics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Byers, A. D. (2018). Graceful Colorings and Connection in Graphs. (Doctoral Dissertation). Western Michigan University. Retrieved from https://scholarworks.wmich.edu/dissertations/3308
Chicago Manual of Style (16th Edition):
Byers, Alexis D. “Graceful Colorings and Connection in Graphs.” 2018. Doctoral Dissertation, Western Michigan University. Accessed April 21, 2021.
https://scholarworks.wmich.edu/dissertations/3308.
MLA Handbook (7th Edition):
Byers, Alexis D. “Graceful Colorings and Connection in Graphs.” 2018. Web. 21 Apr 2021.
Vancouver:
Byers AD. Graceful Colorings and Connection in Graphs. [Internet] [Doctoral dissertation]. Western Michigan University; 2018. [cited 2021 Apr 21].
Available from: https://scholarworks.wmich.edu/dissertations/3308.
Council of Science Editors:
Byers AD. Graceful Colorings and Connection in Graphs. [Doctoral Dissertation]. Western Michigan University; 2018. Available from: https://scholarworks.wmich.edu/dissertations/3308
22.
Skrepetos, Dimitrios.
Shortest Paths in Geometric Intersection Graphs.
Degree: 2018, University of Waterloo
URL: http://hdl.handle.net/10012/13454
► This thesis studies shortest paths in geometric intersection graphs, which can model, among others, ad-hoc communication and transportation networks. First, we consider two classical problems…
(more)
▼ This thesis studies shortest paths in geometric intersection graphs, which can model, among others, ad-hoc communication and transportation networks. First, we consider two classical problems in the field of algorithms, namely Single-Source Shortest Paths (SSSP) and All-Pairs Shortest Paths (APSP). In SSSP we want to compute the shortest paths from one vertex of a graph to all other vertices, while in APSP we aim to find the shortest path between every pair of vertices. Although there is a vast literature for these problems in many graph classes, the case of geometric intersection graphs has been only partially addressed.
In unweighted unit-disk graphs, we show that we can solve SSSP in linear time, after presorting the disk centers with respect to their coordinates. Furthermore, we give the first (slightly) subquadratic-time APSP algorithm by using our new SSSP result, bit tricks, and a shifted-grid-based decomposition technique.
In unweighted, undirected geometric intersection graphs, we present a simple and general technique that reduces APSP to static, offline intersection detection. Consequently, we give fast APSP algorithms for intersection graphs of arbitrary disks, axis-aligned line segments, arbitrary line segments, d-dimensional axis-aligned boxes, and d-dimensional axis-aligned unit hypercubes. We also provide a near-linear-time SSSP algorithm for intersection graphs of axis-aligned line segments by a reduction to dynamic orthogonal point location.
Then, we study two problems that have received considerable attention lately. The first is that of computing the diameter of a graph, i.e., the longest shortest-path distance between any two vertices. In the second, we want to preprocess a graph into a data structure, called distance oracle, such that the shortest path (or its length) between any two query vertices can be found quickly. Since these problems are often too costly to solve exactly, we study their approximate versions.
Following a long line of research, we employ Voronoi diagrams to compute a (1+epsilon)-approximation of the diameter of an undirected, non-negatively-weighted planar graph in time near linear in the input size and polynomial in 1/epsilon. The previously best solution had exponential dependency on the latter. Using similar techniques, we can also construct the first (1+epsilon)-approximate distance oracles with similar preprocessing time and space and only O(log(1/ε)) query time.
In weighted unit-disk graphs, we present the first near-linear-time (1+epsilon)-approximation algorithm for the diameter and for other related problems, such as the radius and the bichromatic closest pair. To do so, we combine techniques from computational geometry and planar graphs, namely well-separated pair decompositions and shortest-path separators. We also show how to extend our approach to obtain O(1)-query-time (1+epsilon)-approximate distance oracles with near linear preprocessing time and space. Then, we apply these oracles, along with additional ideas, to build a data…
Subjects/Keywords: shortest paths; unit-disk graphs; planar graphs; geometric intersection graphs; diameter
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Skrepetos, D. (2018). Shortest Paths in Geometric Intersection Graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/13454
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Skrepetos, Dimitrios. “Shortest Paths in Geometric Intersection Graphs.” 2018. Thesis, University of Waterloo. Accessed April 21, 2021.
http://hdl.handle.net/10012/13454.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Skrepetos, Dimitrios. “Shortest Paths in Geometric Intersection Graphs.” 2018. Web. 21 Apr 2021.
Vancouver:
Skrepetos D. Shortest Paths in Geometric Intersection Graphs. [Internet] [Thesis]. University of Waterloo; 2018. [cited 2021 Apr 21].
Available from: http://hdl.handle.net/10012/13454.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Skrepetos D. Shortest Paths in Geometric Intersection Graphs. [Thesis]. University of Waterloo; 2018. Available from: http://hdl.handle.net/10012/13454
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Kansas
23.
Adams, Kevin Daniel.
On Kernels, β-graphs, and β-graph Sequences of Digraphs.
Degree: MA, Mathematics, 2015, University of Kansas
URL: http://hdl.handle.net/1808/19005
► We begin by investigating some conditions determining the existence of kernels in various classes of directed graphs, most notably in oriented trees, grid graphs, and…
(more)
▼ We begin by investigating some conditions determining the existence of kernels in various classes of directed
graphs, most notably in oriented trees, grid
graphs, and oriented cycles. The question of uniqueness of these kernels is also handled. Attention is then shifted to γ-
graphs, structures associated to the minimum dominating sets of undirected
graphs. I define the β-graph of a given digraph analogously, involving the minimum absorbant sets. Finally, attention is given to iterative construction of β-
graphs, with an attempt to characterize for what classes of digraphs these β-sequences terminate.
Advisors/Committee Members: Bayer, Margaret (advisor), Bayer, Margaret (cmtemember), Martin, Jeremy L (cmtemember), Jiang, Yunfeng (cmtemember).
Subjects/Keywords: Mathematics; Absorbant Sets; Directed Graphs; Dominating Sets; β-graphs; 𝛾-graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Adams, K. D. (2015). On Kernels, β-graphs, and β-graph Sequences of Digraphs. (Masters Thesis). University of Kansas. Retrieved from http://hdl.handle.net/1808/19005
Chicago Manual of Style (16th Edition):
Adams, Kevin Daniel. “On Kernels, β-graphs, and β-graph Sequences of Digraphs.” 2015. Masters Thesis, University of Kansas. Accessed April 21, 2021.
http://hdl.handle.net/1808/19005.
MLA Handbook (7th Edition):
Adams, Kevin Daniel. “On Kernels, β-graphs, and β-graph Sequences of Digraphs.” 2015. Web. 21 Apr 2021.
Vancouver:
Adams KD. On Kernels, β-graphs, and β-graph Sequences of Digraphs. [Internet] [Masters thesis]. University of Kansas; 2015. [cited 2021 Apr 21].
Available from: http://hdl.handle.net/1808/19005.
Council of Science Editors:
Adams KD. On Kernels, β-graphs, and β-graph Sequences of Digraphs. [Masters Thesis]. University of Kansas; 2015. Available from: http://hdl.handle.net/1808/19005
Indian Institute of Science
24.
Mathew, Rogers.
Boxicity And Cubicity : A Study On Special Classes Of Graphs.
Degree: PhD, Faculty of Engineering, 2014, Indian Institute of Science
URL: http://etd.iisc.ac.in/handle/2005/2320
► Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping…
(more)
▼ Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval
graphs find application in diverse fields ranging from DNA analysis to VLSI design.
An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. Thus, an interval is a 1-box and a unit length interval is a 1-cube. A graph G has a k-box representation, if G is an intersection graph of a family of k-boxes in Rk. Similarly, G has a k-cube representation, if G is an intersection graph of a family of k-cubes in Rk. The boxicity of G, denoted by box(G), is the minimum positive integer k such that G has a k-box representation. Similarly, the cubicity of G, denoted by cub(G), is the minimum
positive integer k such that G has a k-cube representation. Thus, interval
graphs are the
graphs with boxicity equal to 1 and unit interval
graphs are the
graphs with cubicity equal to 1.
The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NP-complete even for a small positive integer k. Box representation of
graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NP-hard problems become polynomial time solvable.
Attempts to find efficient box and cube representations for special classes of
graphs can be seen in the literature. Scheinerman [6] showed that the boxicity of outerplanar
graphs is at most 2. Thomassen [7] proved that the boxicity of planar
graphs is bounded from above by 3. Cube representations of special classes of
graphs like hypercubes and complete multipartite
graphs were investigated in [5, 3, 4]. In this thesis, we present several bounds for boxicity and cubicity of special classes of
graphs in terms of other graph parameters. The following are the main results shown in this work.
1. It was shown in [2] that, for a graph G with maximum degree Δ, cub(G) ≤ [4(Δ+ 1) log n]. We show that, for a k-degenerate graph G, cub(G) ≤ (k + 2)[2e log n]. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight up to a constant factor.
2. For a k-degenerate graph G, we give an efficient deterministic algorithm that runs in O(n2k) time to output an O(k log n) dimensional cube representation.
3. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We show that if crossing number of G is t, then box(G) is O(t1/4 log3/4 t). This bound is tight up to a factor of O((log t)1/4 ).
4. We prove that almost all
graphs have cubicity O(dav log n), where dav denotes the average…
Advisors/Committee Members: Chandran, L Sunil (advisor).
Subjects/Keywords: Graphs; Boxicity; Leaf Powers; Random Grpahs; Line Graphs; Chordal Bipartite Graphs; Random Graphs; k-chordal Graphs; Crossing Number; Cubicity; Geometry
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Mathew, R. (2014). Boxicity And Cubicity : A Study On Special Classes Of Graphs. (Doctoral Dissertation). Indian Institute of Science. Retrieved from http://etd.iisc.ac.in/handle/2005/2320
Chicago Manual of Style (16th Edition):
Mathew, Rogers. “Boxicity And Cubicity : A Study On Special Classes Of Graphs.” 2014. Doctoral Dissertation, Indian Institute of Science. Accessed April 21, 2021.
http://etd.iisc.ac.in/handle/2005/2320.
MLA Handbook (7th Edition):
Mathew, Rogers. “Boxicity And Cubicity : A Study On Special Classes Of Graphs.” 2014. Web. 21 Apr 2021.
Vancouver:
Mathew R. Boxicity And Cubicity : A Study On Special Classes Of Graphs. [Internet] [Doctoral dissertation]. Indian Institute of Science; 2014. [cited 2021 Apr 21].
Available from: http://etd.iisc.ac.in/handle/2005/2320.
Council of Science Editors:
Mathew R. Boxicity And Cubicity : A Study On Special Classes Of Graphs. [Doctoral Dissertation]. Indian Institute of Science; 2014. Available from: http://etd.iisc.ac.in/handle/2005/2320
University of Tennessee – Knoxville
25.
McClurkin, Grace Elizabeth.
Generalizations and Variations of the Zero-Divisor Graph.
Degree: 2017, University of Tennessee – Knoxville
URL: https://trace.tennessee.edu/utk_graddiss/4701
► We explore generalizations and variations of the zero-divisor graph on commutative rings with identity. A zero-divisor graph is a graph whose vertex set is the…
(more)
▼ We explore generalizations and variations of the zero-divisor graph on commutative rings with identity. A zero-divisor graph is a graph whose vertex set is the nonzero zero-divisors of a ring, wherein two distinct vertices are adjacent if their product is zero. Variations of the zero-divisor graph are created by changing the vertex set, the edge condition, or both. The annihilator graph and the extended zero-divisor graph are both variations that change the edge condition, whereas the compressed graph and ideal-based graph change the vertex set. By combining these concepts, we define and investigate graphs where both the vertex set and edge condition are changed such as compressed annihilator graphs and ideal-based extended zero-divisor graphs.
We then generalize these variations by defining congruence-based versions of the annihilator graph and extended zero-divisor graph. Many of the previous graphs are shown to fit this more general framework. The congruence-based version of a graph has a vertex set equal to the equivalence classes of some multiplicative congruence relation, with the edge condition determined separately. We prove several foundational properties for these and additionally look at the relationships between and within the families of congruence-based graphs.
Subjects/Keywords: Commutative Ring Theory; Zero-Divisor Graphs; Congruence-Based Zero-Divisor Graphs; Annihilator Graphs; Extended Zero-Divisor Graphs; Compressed Graphs; Algebra
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
McClurkin, G. E. (2017). Generalizations and Variations of the Zero-Divisor Graph. (Doctoral Dissertation). University of Tennessee – Knoxville. Retrieved from https://trace.tennessee.edu/utk_graddiss/4701
Chicago Manual of Style (16th Edition):
McClurkin, Grace Elizabeth. “Generalizations and Variations of the Zero-Divisor Graph.” 2017. Doctoral Dissertation, University of Tennessee – Knoxville. Accessed April 21, 2021.
https://trace.tennessee.edu/utk_graddiss/4701.
MLA Handbook (7th Edition):
McClurkin, Grace Elizabeth. “Generalizations and Variations of the Zero-Divisor Graph.” 2017. Web. 21 Apr 2021.
Vancouver:
McClurkin GE. Generalizations and Variations of the Zero-Divisor Graph. [Internet] [Doctoral dissertation]. University of Tennessee – Knoxville; 2017. [cited 2021 Apr 21].
Available from: https://trace.tennessee.edu/utk_graddiss/4701.
Council of Science Editors:
McClurkin GE. Generalizations and Variations of the Zero-Divisor Graph. [Doctoral Dissertation]. University of Tennessee – Knoxville; 2017. Available from: https://trace.tennessee.edu/utk_graddiss/4701
Indian Institute of Science
26.
Rajendraprasad, Deepak.
Rainbow Colouring and Some Dimensional Problems in Graph Theory.
Degree: PhD, Faculty of Engineering, 2018, Indian Institute of Science
URL: http://etd.iisc.ac.in/handle/2005/3336
► This thesis touches three different topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is…
(more)
▼ This thesis touches three different topics in graph theory, namely, rainbow colouring, product dimension and boxicity.
Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices is connected by atleast one path in which no two edges are coloured the same. The rainbow connection number of a graph is the minimum number of colours required to rainbow colour it. In this thesis we give upper bounds on rainbow connection number based on graph invariants like minimum degree, vertex connectivity, and radius. We also give some computational complexity results for special graph classes.
Product dimension The product dimension or Prague dimension of a graph G is the smallest natural number k such that G is an induced subgraph of a direct product of k complete
graphs. In this thesis, we give upper bounds on the product dimension for forests, bounded tree width
graphs and
graphs of bounded degeneracy.
Boxicity and cubicity The boxicity (cubicity of a graph G is the smallest natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes(axis-parallel unit cubes) in Rk .In this thesis, we study the boxicity and the cubicity of Cartesian, strong and direct products of
graphs and give estimates on the boxicity and the cubicity of a product graph based on invariants of the component
graphs.
Separation dimension The separation dimension of a hypergraph H is the smallest natural number k for which the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyper plane normal to one of the axes. While studying the boxicity of line
graphs, we noticed that a box representation of the line graph of a hypergraph has a nice geometric interpretation. Hence we introduced this new parameter and did an extensive study of the same.
Advisors/Committee Members: Chandran, L Sunil (advisor).
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 »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Rajendraprasad, D. (2018). Rainbow Colouring and Some Dimensional Problems in Graph Theory. (Doctoral Dissertation). Indian Institute of Science. Retrieved from http://etd.iisc.ac.in/handle/2005/3336
Chicago Manual of Style (16th Edition):
Rajendraprasad, Deepak. “Rainbow Colouring and Some Dimensional Problems in Graph Theory.” 2018. Doctoral Dissertation, Indian Institute of Science. Accessed April 21, 2021.
http://etd.iisc.ac.in/handle/2005/3336.
MLA Handbook (7th Edition):
Rajendraprasad, Deepak. “Rainbow Colouring and Some Dimensional Problems in Graph Theory.” 2018. Web. 21 Apr 2021.
Vancouver:
Rajendraprasad D. Rainbow Colouring and Some Dimensional Problems in Graph Theory. [Internet] [Doctoral dissertation]. Indian Institute of Science; 2018. [cited 2021 Apr 21].
Available from: http://etd.iisc.ac.in/handle/2005/3336.
Council of Science Editors:
Rajendraprasad D. Rainbow Colouring and Some Dimensional Problems in Graph Theory. [Doctoral Dissertation]. Indian Institute of Science; 2018. Available from: http://etd.iisc.ac.in/handle/2005/3336
Indian Institute of Science
27.
Khopkar, Abhijeet.
Computational And Combinatorial Problems On Some Geometric Proximity Graphs.
Degree: PhD, Faculty of Engineering, 2017, Indian Institute of Science
URL: http://etd.iisc.ac.in/handle/2005/2622
► In this thesis, we focus on the study of computational and combinatorial problems on various geometric proximity graphs. Delaunay and Gabriel graphs are widely studied…
(more)
▼ In this thesis, we focus on the study of computational and combinatorial problems on various geometric proximity
graphs. Delaunay and Gabriel
graphs are widely studied geometric proximity structures. These
graphs have been extensively studied for their applications in wireless networks. Motivated by the applications in localized wireless routing, relaxed versions of these
graphs known as Locally Delaunay
Graphs (LDGs) and Locally Gabriel
Graphs(LGGs) were proposed.
A geometric graph G=(V,E)is called a Locally Gabriel Graph if for every( u,v) ϵ E the disk with uv as diameter does not contain any neighbor of u or v in G. Thus, two edges (u, v) and(u, w)where u,v,w ϵ V conflict with each other if ∠uwv ≥ or ∠uvw≥π and cannot co-exist in an LGG. We propose another generalization of LGGs called Generalized locally Gabriel
Graphs(GLGGs)in the context when certain edges are forbidden in the graph. For a given geometric graph G=(V,E), we define G′=(V,E′) as GLGG if G′is an LGG and E′⊆E. Unlike a Gabriel Graph ,there is no unique LGG or GLGG for a given point set because no edge is necessarily included or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. While Gabriel
graphs are planar
graphs, there exist LGGs with super linear number of edges. Also, there exist point sets where a Gabriel graph has dilation of Ω(√n)and there exist LGGs on the same point sets with dilation O(1). We study these
graphs for various parameters like edge complexity(the maximum number of edges in these
graphs),size of an independent set and dilation. We show that computing an edge
maximum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with minimum dilation is NP-hard. Then, we give an algorithm to verify whether a given geometric graph G=(V,E)is an LGG with running time O(ElogV+ V).
We show that any LGG on n vertices has an independent set of size Ω(√nlogn). We show that there exists point sets with n points such that any LGG on it has dilation Ω(√n) that matches with the known upper bound. Then, we study some greedy heuristics to compute LGGs with experimental evaluation. Experimental evaluations for the points on a uniform grid and random point sets suggest that there exist LGGs with super-linear number of edges along with an independent set of near-linear size. Unit distance
graphs(UDGs) are well studied geometric
graphs. In this graph, an edge exists between two points if and only if the Euclidean distance between the points is unity. UDGs have been studied extensively for various properties most notably for their edge complexity and chromatic number. These
graphs have also been studied for various special point sets most notably the case when the points are in convex position. Note that the UDGs form a sub class of the LGGs. UDGs/LGGs on convex point sets have O(nlogn) edges. The best known lower bound on the edge complexity of these
graphs is 2n−7 when all the points are in convex position. A bipartite graph…
Advisors/Committee Members: Govindrajan, Sathish (advisor).
Subjects/Keywords: Geometric Proximity Graphs; Computational Geometry; Geometric Graphs; Gabriel Graphs; Locally Gabriel Graphs; Unit Distance Graphs; Ordered Bipartite Graphs; Convex Point Sets; Combinatorial Geometry; Locally Gabriel Geometric Graphs; Computer Science
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Khopkar, A. (2017). Computational And Combinatorial Problems On Some Geometric Proximity Graphs. (Doctoral Dissertation). Indian Institute of Science. Retrieved from http://etd.iisc.ac.in/handle/2005/2622
Chicago Manual of Style (16th Edition):
Khopkar, Abhijeet. “Computational And Combinatorial Problems On Some Geometric Proximity Graphs.” 2017. Doctoral Dissertation, Indian Institute of Science. Accessed April 21, 2021.
http://etd.iisc.ac.in/handle/2005/2622.
MLA Handbook (7th Edition):
Khopkar, Abhijeet. “Computational And Combinatorial Problems On Some Geometric Proximity Graphs.” 2017. Web. 21 Apr 2021.
Vancouver:
Khopkar A. Computational And Combinatorial Problems On Some Geometric Proximity Graphs. [Internet] [Doctoral dissertation]. Indian Institute of Science; 2017. [cited 2021 Apr 21].
Available from: http://etd.iisc.ac.in/handle/2005/2622.
Council of Science Editors:
Khopkar A. Computational And Combinatorial Problems On Some Geometric Proximity Graphs. [Doctoral Dissertation]. Indian Institute of Science; 2017. Available from: http://etd.iisc.ac.in/handle/2005/2622
Temple University
28.
Gidelew, Getnet Abebe.
Topics in Harmonic Analysis on Combinatorial Graphs.
Degree: PhD, 2014, Temple University
URL: http://digital.library.temple.edu/u?/p245801coll10,262601
► Mathematics
In recent years harmonic analysis on combinatorial graphs has attracted considerable attention. The interest is stimulated in part by multiple existing and potential applications…
(more)
▼ Mathematics
In recent years harmonic analysis on combinatorial graphs has attracted considerable attention. The interest is stimulated in part by multiple existing and potential applications of analysis on graphs to information theory, signal analysis, image processing, computer sciences, learning theory, and astronomy. My thesis is devoted to sampling, interpolation, approximation, and multi-resolution on graphs. The results in the existing literature concern mainly with these theories on unweighted graphs. My main objective is to extend existing theories and obtain new results about sampling, interpolation, approximation, and multi-resolution on general combinatorial graphs such as directed, undirected and weighted.
Temple University – Theses
Advisors/Committee Members: Pesenson, Isaac Z.;, Berhanu, Shiferaw, Mendoza, Gerardo A., Nowak, Krzysztof;.
Subjects/Keywords: Mathematics;
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Gidelew, G. A. (2014). Topics in Harmonic Analysis on Combinatorial Graphs. (Doctoral Dissertation). Temple University. Retrieved from http://digital.library.temple.edu/u?/p245801coll10,262601
Chicago Manual of Style (16th Edition):
Gidelew, Getnet Abebe. “Topics in Harmonic Analysis on Combinatorial Graphs.” 2014. Doctoral Dissertation, Temple University. Accessed April 21, 2021.
http://digital.library.temple.edu/u?/p245801coll10,262601.
MLA Handbook (7th Edition):
Gidelew, Getnet Abebe. “Topics in Harmonic Analysis on Combinatorial Graphs.” 2014. Web. 21 Apr 2021.
Vancouver:
Gidelew GA. Topics in Harmonic Analysis on Combinatorial Graphs. [Internet] [Doctoral dissertation]. Temple University; 2014. [cited 2021 Apr 21].
Available from: http://digital.library.temple.edu/u?/p245801coll10,262601.
Council of Science Editors:
Gidelew GA. Topics in Harmonic Analysis on Combinatorial Graphs. [Doctoral Dissertation]. Temple University; 2014. Available from: http://digital.library.temple.edu/u?/p245801coll10,262601
Anna University
29.
Sankar, K.
Study on graceful harmonious and cordial
graphs; -.
Degree: Science and Humanities, 2014, Anna University
URL: http://shodhganga.inflibnet.ac.in/handle/10603/24801
► Much interest in graph labelings began in mid 1960s with the conjecture of Ringel and a paper by Rosa The popular Ringel Kotzig conjecture that…
(more)
▼ Much interest in graph labelings began in mid 1960s
with the conjecture of Ringel and a paper by Rosa The popular
Ringel Kotzig conjecture that all trees are graceful remains
unsettled In his classic paper Rosa introduced and#946;valuation
and#945;valuation and other labelings as a tool to decompose
complete graphs This labeling was later called graceful by Golomb
and now this is the term most widely used Graham and Sloane
introduced harmonious labeling in connection with their study on
additive bases problem stemming from error correcting codes Over
the period variations of graceful and harmonious labeling were
studied with different motivations Chang introduced elegant
labeling as a variation of harmonious labeling Cordial labeling was
introduced by Cahit as a variation of both graceful and harmonious
labeling Over the period of four decades the field of graph
labeling has experienced rapid growth However the fundamental
understanding that the characterization of graceful and other
labeled graphs appears to be one of the most difficult and hard
problems in graph theory
-
Advisors/Committee Members: Sethuraman, G.
Subjects/Keywords: Cordial graphs; Graceful graphs; Graceful labeling; Harmonious graphs; Harmonious labeling; Mathematics; Science and humanities
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Sankar, K. (2014). Study on graceful harmonious and cordial
graphs; -. (Thesis). Anna University. Retrieved from http://shodhganga.inflibnet.ac.in/handle/10603/24801
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Sankar, K. “Study on graceful harmonious and cordial
graphs; -.” 2014. Thesis, Anna University. Accessed April 21, 2021.
http://shodhganga.inflibnet.ac.in/handle/10603/24801.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Sankar, K. “Study on graceful harmonious and cordial
graphs; -.” 2014. Web. 21 Apr 2021.
Vancouver:
Sankar K. Study on graceful harmonious and cordial
graphs; -. [Internet] [Thesis]. Anna University; 2014. [cited 2021 Apr 21].
Available from: http://shodhganga.inflibnet.ac.in/handle/10603/24801.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Sankar K. Study on graceful harmonious and cordial
graphs; -. [Thesis]. Anna University; 2014. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/24801
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Georgia Tech
30.
Xie, Shijie.
6-connected graphs are two-three linked.
Degree: PhD, Mathematics, 2019, Georgia Tech
URL: http://hdl.handle.net/1853/62273
► Let G be a graph and a0, a1, a2, b1, and b2 be distinct vertices of G. Motivated by their work on Four Color Theorem,…
(more)
▼ Let G be a graph and a
0, a
1, a
2, b
1, and b
2 be distinct vertices of G. Motivated by their work on Four Color Theorem, Hadwiger's conjecture for K
6, and J\o rgensen's conjecture, Robertson and Seymour asked when does G contain disjoint connected subgraphs G
1, G
2, such that {a
0, a
1, a
2}\subseteq V(G
1) and {b
1, b
2}\subseteq V(G
2). We prove that if G is 6-connected then such G
1,G
2 exist. Joint work with Robin Thomas and Xingxing Yu.
Advisors/Committee Members: Yu, Xingxing (advisor), Thomas, Robin (committee member), Tetali, Prasad (committee member), Peng, Richard (committee member), Warnke, Lutz (committee member).
Subjects/Keywords: Graph theory; Disjoint paths in graphs; Two-three linked graphs; 6-connected graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Xie, S. (2019). 6-connected graphs are two-three linked. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/62273
Chicago Manual of Style (16th Edition):
Xie, Shijie. “6-connected graphs are two-three linked.” 2019. Doctoral Dissertation, Georgia Tech. Accessed April 21, 2021.
http://hdl.handle.net/1853/62273.
MLA Handbook (7th Edition):
Xie, Shijie. “6-connected graphs are two-three linked.” 2019. Web. 21 Apr 2021.
Vancouver:
Xie S. 6-connected graphs are two-three linked. [Internet] [Doctoral dissertation]. Georgia Tech; 2019. [cited 2021 Apr 21].
Available from: http://hdl.handle.net/1853/62273.
Council of Science Editors:
Xie S. 6-connected graphs are two-three linked. [Doctoral Dissertation]. Georgia Tech; 2019. Available from: http://hdl.handle.net/1853/62273
◁ [1] [2] [3] [4] [5] … [62] ▶
. 
Open Access Theses and Dissertations
