Spelling suggestions: "subject:"aroduct agraphs"" "subject:"aroduct digraphs""
1 |
Dot Product Graphs and Their Applications to EcologyBailey, Sean 01 May 2013 (has links)
During the past few decades, examinations of social, biological, and communication networks have taken on increased attention. While numerous models of these networks have arisen, some have lacked visual representations. This is particularly true in ecology, where scientists have often been restricted to at most three dimensions when creating graphical representations of pattern and process. I will introduce an application of dot product representation graphs that allows scientists to view the high dimensional connections in ecological networks. Using actual data, example graphs will be developed and analyzed using key measures of graph theory.
|
2 |
To Dot Product Graphs and BeyondBailey, Sean 01 May 2016 (has links)
We will introduce three new classes of graphs; namely bipartite dot product graphs, probe dot product graphs, and combinatorial orthogonal graphs. All of these representations were inspired by a vector representation known as a dot product representation.
Given a bipartite graph G = (X, Y, E), the bipartite dot product representation of G is a function ƒ : X ∪ Y → Rk and a positive threshold t such that for any κ ∈ Χ and γ ∈ Υ , κγ ∈ ε if and only if f(κ) · f(γ) ≥ t. The minimum k such that a bipartite dot product representation exists for G is the bipartite dot product dimension of G, denoted bdp(G). We will show that such representations exist for all bipartite graphs as well as give an upper bound for the bipartite dot product dimension of any graph. We will also characterize the bipartite graphs of bipartite dot product dimension 1 by their forbidden subgraphs.
An undirected graph G = (V, E) is a probe C graph if its vertex set can be parti-tioned into two sets, N (nonprobes) and P (probes) where N is independent and there exists E' ⊆ N × N such that G' = (V, E ∪ E) is a C graph. In this dissertation we introduce probe k-dot product graphs and characterize (at least partially) probe 1-dot product graphs in terms of forbidden subgraphs and certain 2-SAT formulas. These characterizations are given for the very different circumstances: when the partition into probes and nonprobes is given, and when the partition is not given.
Vectors κ = (κ1, κ2, . . . , κn)T and γ = (γ1, γ2, . . . , γn)T are combinatorially orthogonal if |{i : κiγi = 0}| ≠ 1. An undirected graph G = (V, E) is a combinatorial orthogonal graph if there exists ƒ : V → Rn for some n ∈ Ν such that for any u, υ &Isin; V , uv ∉ E iff ƒ(u) and ƒ(v) are combinatorially orthogonal. These representations can also be limited to a mapping g : V → {0, 1}n such that for any u,v ∈ V , uv ∉ E iff g(u) · g(v) = 1. We will show that every graph has a combinatorial orthogonal representation. We will also state the minimum dimension necessary to generate such a representation for specific classes of graphs.
|
3 |
Rainbow Connection Number Of Graph Power And Graph ProductsArunselvan, R 11 1900 (has links) (PDF)
The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.
|
4 |
Sobre alianças defensivas e ofensivas globais em alguns produtos de grafos e grafos simpliciais / Defensive and offensive alliance at product graphs and simplicial graphsSilva, Leila Roling Scariot da 30 October 2015 (has links)
Submitted by Cláudia Bueno (claudiamoura18@gmail.com) on 2016-03-04T16:57:18Z
No. of bitstreams: 2
Tese - Leila Roling Scariot da Silva - 2015.pdf: 821704 bytes, checksum: afe6afd0f3cea67708178512b59c2c09 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-03-07T12:10:47Z (GMT) No. of bitstreams: 2
Tese - Leila Roling Scariot da Silva - 2015.pdf: 821704 bytes, checksum: afe6afd0f3cea67708178512b59c2c09 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-07T12:10:47Z (GMT). No. of bitstreams: 2
Tese - Leila Roling Scariot da Silva - 2015.pdf: 821704 bytes, checksum: afe6afd0f3cea67708178512b59c2c09 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2015-10-30 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / Given a graph G, a defensive alliance of a set of vertices A⊆V(G) satisfying the condition
that for each v ∈ A, |N[v] ∩ A| ≤ |N[v] − A|. The set S is an offensive alliance if the
inaquality holds for every v ∈ N[S]−S. A alliance A is called global if is also a dominant
set. In this paper, we establish lower bounds for Simplicial Graphs and further give closed
formulas and upper bounds to decide the global, defensive, offensive, alliance numbers
for lexicographic product of paths, cycles, stars and complete graphs. We establish a
relationship to global defensive alliance numbers and complementary prism product to
graphs. / A aliança é um conceito introduzido por Hedetniemi, Hedetniemi e Kristiansen em 2004,
onde foram classificadas em defensiva, ofensiva ou poderosa. Informalmente, podemos
entender uma aliança como uma coleção de entidades tal que a união é mais forte do que
o indivíduo. Uma aliança, de qualquer entidade, pode tanto servir para proteção contra
ataques, quanto para aumentar a capacidade para atacar outras entidades. Toda aliança é
global se for um conjunto dominante. A complexidade computacional e aplicações para
a defesa nacional, redes de computadores, distribuição computacional e redes sociais são
exemplos que motivam os estudos sobre alianças em grafos. Neste trabalho nós lidamos
com alguns limites e fórmulas fechadas de algumas famílias de produto lexicográfico
para obter o número mínimo da aliança defensiva global e aliança ofensiva global e
apresentamos uma relação entre grafos gerais e sua aliança defensiva global para prisma
complementar, bem como obtivemos limites para algumas famílias de grafos como grafos
simplicias.
|
5 |
Kings in the Direct Product of DigraphsNorge, Morgan 01 January 2019 (has links)
A k-king in a digraph D is a vertex that can reach every other vertex in D by a directed path of length at most k. A king is a vertex that is a k-king for some k. We will look at kings in the direct product of digraphs and characterize a relationship between kings in the product and kings in the factors. This is a continuation of a project in which a similar characterization is found for the cartesian product of digraphs, the strong product of digraphs, and the lexicographic product of digraphs.
|
6 |
Rainbow Colouring and Some Dimensional Problems in Graph TheoryRajendraprasad, Deepak January 2013 (has links) (PDF)
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.
|
Page generated in 0.0418 seconds