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.
| Identifer | oai:union.ndltd.org:UTAHS/oai:digitalcommons.usu.edu:etd-6064 |
| Date | 01 May 2016 |
| Creators | Bailey, Sean |
| Publisher | DigitalCommons@USU |
| Source Sets | Utah State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | All Graduate Theses and Dissertations |
| Rights | Copyright for this work is held by the author. Transmission or reproduction of materials protected by copyright beyond that allowed by fair use requires the written permission of the copyright owners. Works not in the public domain cannot be commercially exploited without permission of the copyright owner. Responsibility for any use rests exclusively with the user. For more information contact Andrew Wesolek (andrew.wesolek@usu.edu). |
Page generated in 0.0026 seconds