Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 17 of 17 for “"Mixed Graphs"”.
-
Postman Problems on Mixed Graphs
The <i>mixed postman problem</i> consists of finding a minimum cost tour of a mixed graph <i>M</i> = (<i>V</i>,<i>E</i>,<i>A</i>) traversing all its edges and arcs at least once. We prove that two well-known linear programming relaxations of this problem are equivalent. The <i>extra cost</i> of a …
-
Chromatic polynomials of mixed graphs
Let G = (V,A,E) be a mixed graph and co : V → {1, 2,...,λ} a function such that co is a proper colouring of the underlying graph, Und(G), and co(u) ≠ co(y) when co(v) = co(x), for every pair of arcs (u,v) and (x,y). Such a function is called a proper oriented λ − colouring of G. The number of …
-
Extremal Directed And Mixed Graphs
… the context of directed and partially directed graphs. A directed graph or mixed graph $G$ is $k$-geodetic if there is no pair of vertices $u,v$ of $G$ such that there exist distinct non-backtracking walks with length $\leq k$ in $G$ from $u$ to $v$. The order of a $k$-geodetic digraph with …
-
Homomorphisms of (j, k)-mixed graphs
A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed …
-
Gamma-Switchable 2-Colourings of (m,n)-Mixed Graphs
A $(m,n)$-mixed graph is a mixed graph whose edges are assigned one of $m$ colours, and whose arcs are assigned one of $n$ colours. Let $G$ be a $(m,n)$-mixed graph and $\pi=(\alpha,\beta,\gamma_1,\gamma_2,\ldots,\gamma_n)$ be a $(n+2)$-tuple of permutations from $S_m \times S_n \times S_2^n$. We …
-
Partially Oriented 6-star Decomposition of Some Complete Mixed Graphs
Let $M_v$ denotes a complete mixed graph on $v$ vertices, and let $S_6^i$ denotes the partial orientation of the 6-star with twice as many arcs as edges. In this work, we state and prove the necessary and sufficient conditions for the existence of $\lambda$-fold decomposition of a complete mixed …
-
Decompositions of Mixed Graphs with Partial Orientations of the P<sub>4</sub>.
… each part of the partition is isomorphic to G. A mixed graph on V vertices is an ordered pair (V,C), where V is a set of vertices, |V| = v, and C is a set of ordered and unordered pairs, denoted (x, y) and [x, y] respectively, of elements of V [8]. An ordered pair (x, y) ∈ C is called an arc of …
-
Decompositions of the Complete Mixed Graph by Mixed Stars
In the study of mixed graphs, a common question is: What are the necessary and suffcient conditions for the existence of a decomposition of the complete mixed graph into isomorphic copies of a given mixed graph? Since the complete mixed graph has twice as many arcs as edges, then an obvious …
-
Bicyclic Mixed Triple Systems.
… condition for the existence of a bicyclic mixed triple system based on the three possible partial orientations of the 3-cycle with twice as many arcs as edges. We also explore the existence of rotational and reverse mixed triple systems. Our principal proof technique applied is the …
-
Algorithm design and engineering for graph connectivity problems
… some notions of graph connectivity in directed graphs and mixed graphs. The edge and vertex connectivity of a graph are important measures of its resilience as a network. There is a great variety of real-life relations that can be modeled by graphs. A few of the most notable examples include …
-
Algebraic and Combinatorial Applications in Systems and Evolutionary Biology
… differential equations given by directed graphs, optimal phylogenetic consensus trees, and singularities arising from linear structural equation models given by acyclic mixed graphs. Specifically, for the first algebraic problem, we introduce a polyhedral geometry tool called a mixed …
-
Matrix Formulations of Matching Problems
… by a branching in the associated graph. A mixed graph has both undirected and directed edges, and the matching forest problem for mixed graphs, introduced by Giles, is a generalization of the matching problem and the branching problem. A mixed graph can be represented by the matching forest …
-
Graphical representation of independence structures
… this thesis we describe subclasses of a class of graphs with three types of edges, called loopless mixed graphs (LMGs). The class of LMGs contains almost all known classes of graphs used in the literature of graphical Markov models. We focus in particular on the subclass of ribbonless graphs …
-
Diameter, Girth And Other Properties Of Highly Symmetric Graphs
… with the unifying theme being the properties of graphs which have a high degree of symmetry. In the degree-diameter problem, we consider the question of finding asymptotically large graphs of given degree and diameter. We improve a number of the current best published results in the case of …
-
Algebraic properties of linear structural equation models
… \emph{HTC-identifiable graph}. HTC-identifiable graphs are a large family of graphs known to be generically identifiable. We prove that a mixed graphs is HTC-identifiable if and only if all the parameters in the model can be recovered from the covariance matrix using straightforward linear …
-
Linear Structural Equation Models with Non-Gaussian Errors: Estimation and Discovery
… considered in this section correspond to general mixed graphs. We then consider the problem of estimating the underlying structure. Most of the previous work on causal discovery focuses on estimating an equivalence class of graphs rather than a specific graph. However, Shimizu et al. (2016) show …
-
The Last of the Mixed Triple Systems.
… we consider the decomposition of the complete mixed graph on v vertices denoted Mv, into every possible mixed graph on three vertices which has (like Mv) twice as many arcs as edges. Direct constructions are given in most cases. Decompositions of theλ-fold complete mixed graph λMv, are also …