To see the other types of publications on this topic, follow the link: Chordal graph.
Dissertations / Theses on the topic 'Chordal graph'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 41 dissertations / theses for your research on the topic 'Chordal graph.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Alzaidi, Esraa Raheem. "EXPERIMENTS ON CHORDAL GRAPH HELLIFICATION." Kent State University / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=kent1494430064980414.
Full text
2
Ibarra, Louis Walter. "Dynamic algorithms for chordal and interval graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/NQ58573.pdf.
Full text
3
Bhaduri, Sudipta. "Finding A Maximum Clique of A Chordal Graph by Removing Vertices of Minimum Degree." Kent State University / OhioLINK, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=kent1208869783.
Full text
4
Sacramento, Jonathan. "Computing the leafage of chordal graphs /." Leeds : University of Leeds, School of Computer Studies, 2008. http://www.comp.leeds.ac.uk/fyproj/reports/0708/Sacramento.pdf.
Full text
5
Pogorelcnik, Romain. "Decomposition by complete minimum separators and applications." Thesis, Clermont-Ferrand 2, 2012. http://www.theses.fr/2012CLF22301/document.
Full textAbstract:
Nous avons utilisé la décomposition par séparateurs minimaux complets. Pour décomposer un graphe G, il est nécessaire de trouver les séparateurs minimaux dans le graphe triangulé H correspondant. Dans ce contexte, nos premiers efforts se sont tournés vers la détection de séparateurs minimaux dans un graphe triangulé. Nous avons défini une structure, que nous avons nommée 'atom tree'. Cette dernière est inspirée du 'clique tree' et permet d'obtenir et de représenter les atomes qui sont les produits de la décomposition. Lors de la manipulation de données à l'aide de treillis de Galois, nous avons remarqué que la décomposition par séparateurs minimaux permettait une approche de type `Diviser pour régner' pour les treillis de Galois. La détection des gènes fusionnés, qui est une étape importante pour la compréhension de l'évolution des espèces, nous a permis d'appliquer nos algorithmes de détection de séparateurs minimaux complets, qui nous a permis de détecter et regrouper de manière efficace les gènes fusionnés. Une autre application biologique fut la détection de familles de gènes d'intérêts à partir de données de niveaux d'expression de gènes. La structure de `l'atom tree' nous a permis d'avoir un bon outils de visualisation et de gérer des volumes de données importantesWe worked on clique minimal separator decomposition. In order to compute this decomposition on a graph G we need to compute the minimal separators of its triangulation H. In this context, the first efforts were on finding a clique minimal separators in a chordal graph. We defined a structure called atom tree inspired from the clique tree to compute and represent the final products of the decomposition, called atoms. The purpose of this thesis was to apply this technique on biological data. While we were manipulating this data using Galois lattices, we noticed that the clique minimal separator decomposition allows a divide and conquer approach on Galois lattices. One biological application of this thesis was the detection of fused genes which are important evolutionary events. Using algorithms we produced in the course of along our work we implemented a program called MosaicFinder that allows an efficient detection of this fusion event and their pooling. Another biological application was the extraction of genes of interest using expression level data. The atom tree structure allowed us to have a good visualization of the data and to be able to compute large datasets
6
Odom, Richard M. "Edge completion sequences for classes of chordal graphs." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Service, 1995. http://handle.dtic.mil/100.2/ADA302986.
Full text
7
Carroll, Thomas. "Edge annihilation sequences for classes of chordal graphs." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 1996. http://handle.dtic.mil/100.2/ADA313817.
Full text
8
Altomare, Christian J. "Degree Sequences, Forcibly Chordal Graphs, and Combinatorial Proof Systems." The Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1259546079.
Full text
9
Li, Xuechao. "Chords of longest circuits of graphs." Morgantown, W. Va. : [West Virginia University Libraries], 2001. http://etd.wvu.edu/templates/showETD.cfm?recnum=2141.
Full textAbstract:
Thesis (Ph. D.)--West Virginia University, 2001.Title from document title page. Document formatted into pages; contains vi, 57 p. : ill. Includes abstract. Includes bibliographical references (p. 56-57).
10
Krishnamurthy, Chandra Mohan. "The Maximum Induced Matching Problem for Some Subclasses of Weakly Chordal Graphs." University of Dayton / OhioLINK, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=dayton1262624006.
Full text
11
Kammer, Frank [Verfasser], and Torben [Akademischer Betreuer] Hagerup. "Treelike and Chordal Graphs: Algorithms and Generalizations / Frank Kammer. Betreuer: Torben Hagerup." Augsburg : Universität Augsburg, 2012. http://d-nb.info/1077700814/34.
Full text
12
Grußien, Berit. "Capturing Polynomial Time and Logarithmic Space using Modular Decompositions and Limited Recursion." Doctoral thesis, Humboldt-Universität zu Berlin, 2017. http://dx.doi.org/10.18452/18548.
Full textAbstract:
Diese Arbeit leistet Beiträge im Bereich der deskriptiven Komplexitätstheorie. Zunächst beschäftigen wir uns mit der ungelösten Frage, ob es eine Logik gibt, welche die Klasse der Polynomialzeit-Eigenschaften (PTIME) charakterisiert. Wir betrachten Graphklassen, die unter induzierten Teilgraphen abgeschlossen sind. Auf solchen Graphklassen lässt sich die 1976 von Gallai eingeführte modulare Zerlegung anwenden. Graphen, die durch modulare Zerlegung nicht zerlegbar sind, heißen prim. Wir stellen ein neues Werkzeug vor: das Modulare Zerlegungstheorem. Es reduziert (definierbare) Kanonisierung einer Graphklasse C auf (definierbare) Kanonisierung der Klasse aller primen Graphen aus C, die mit binären Relationen auf einer linear geordneten Menge gefärbt sind. Mit Hilfe des Modularen Zerlegungstheorems zeigen wir, dass Fixpunktlogik mit Zählen (FP+C) PTIME auf der Klasse aller Permutationsgraphen und auf der Klasse aller chordalen Komparabilitätsgraphen charakterisiert. Wir beweisen zudem, dass modulare Zerlegungsbäume in Symmetrisch-Transitive-Hüllen-Logik mit Zählen (STC+C) definierbar und damit in logarithmischem Platz berechenbar sind.
Weiterhin definieren wir eine neue Logik für die Komplexitätsklasse Logarithmischer Platz (LOGSPACE). Wir erweitern die Logik erster Stufe mit Zählen um einen Operator, der eine in logarithmischem Platz berechenbare Form der Rekursion erlaubt. Die resultierende Logik LREC ist ausdrucksstärker als die Deterministisch-Transitive-Hüllen-Logik mit Zählen (DTC+C) und echt in FP+C enthalten. Wir zeigen, dass LREC LOGSPACE auf gerichteten Bäumen charakterisiert. Zudem betrachten wir eine Erweiterung LREC= von LREC, die sich gegenüber LREC durch bessere Abschlusseigenschaften auszeichnet und im Gegensatz zu LREC ausdrucksstärker als die Symmetrisch-Transitive-Hüllen-Logik (STC) ist. Wir beweisen, dass LREC= LOGSPACE sowohl auf der Klasse der Intervallgraphen als auch auf der Klasse der chordalen klauenfreien Graphen charakterisiert.This theses is making contributions to the field of descriptive complexity theory. First, we look at the main open problem in this area: the question of whether there exists a logic that captures polynomial time (PTIME). We consider classes of graphs that are closed under taking induced subgraphs. For such graph classes, an effective graph decomposition, called modular decomposition, was introduced by Gallai in 1976. The graphs that are non-decomposable with respect to modular decomposition are called prime. We present a tool, the Modular Decomposition Theorem, that reduces (definable) canonization of a graph class C to (definable) canonization of the class of prime graphs of C that are colored with binary relations on a linearly ordered set. By an application of the Modular Decomposition Theorem, we show that fixed-point logic with counting (FP+C) captures PTIME on the class of permutation graphs and the class of chordal comparability graphs. We also prove that the modular decomposition tree is definable in symmetric transitive closure logic with counting (STC+C), and therefore, computable in logarithmic space. Further, we introduce a new logic for the complexity class logarithmic space (LOGSPACE). We extend first-order logic with counting by a new operator that allows it to formalize a limited form of recursion which can be evaluated in logarithmic space. We prove that the resulting logic LREC is strictly more expressive than deterministic transitive closure logic with counting (DTC+C) and that it is strictly contained in FP+C. We show that LREC captures LOGSPACE on the class of directed trees. We also study an extension LREC= of LREC that has nicer closure properties and that, unlike LREC, is more expressive than symmetric transitive closure logic (STC). We prove that LREC= captures LOGSPACE on the class of interval graphs and on the class of chordal claw-free graphs.
13
Mason, Richard. "A chordal sparsity approach to scalable linear and nonlinear systems analysis." Thesis, University of Oxford, 2015. https://ora.ox.ac.uk/objects/uuid:c4a978aa-185e-4029-a887-6aa2ab9efb37.
Full textAbstract:
In this thesis we investigate how the properties of chordal graphs can be used to exploit sparsity in several optimisation problems that arise in control theory. In particular, we focus on analysis and synthesis problems that involve semidefinite constraints and can be formulated as semidefinite programming (SDP) problems. Using a relationship between chordal graphs and sparse semidefinite matrices, we decompose the semidefinite constraints in the associated SDP problems into multiple, smaller semidefinite constraints along with some additional equality constraints. The benefit of this approach is that for sparse dynamical systems we can solve significantly larger analysis and synthesis problems than is possible using traditional dense methods. We begin by considering the properties of chordal graphs and their connection to sparse positive semidefinite matrices. We then turn our attention to the problem of constructing Lyapunov functions for linear time-invariant (LTI) systems. From this starting point, we derive methods of exploiting chordal sparsity in other analysis problems found in control theory. In particular, this approach is applied to the problem of bounding the input-output properties of systems via the KYP lemma for both continuous and discrete-time systems. We then consider how the properties of chordal graphs can be exploited in the SDPs that arise in static state feedback controller synthesis problems for LTI systems. We show that the sparse inverse property of the maximum determinant completion of a partial positive matrix can be used to design controllers with a pre-specified sparsity pattern. We then consider how to exploit chordal sparsity when designing a static state feedback controller to minimise the H-infinity norm of an LTI system. Next we shift from linear systems to nonlinear systems and develop a chordal sparsity approach to scalable stability analysis of systems with polynomial dynamics using the Sums of Squares (SOS) technique. We develop a method of exploiting chordal sparsity that avoids the computationally costly step of forming the coefficient matrix in the SOS problem. We then apply this method to the problem of constructing Lyapunov functions for systems with correlatively sparse polynomial vector fields. Finally, we conclude by discussing some directions for future research.
14
Acan, Huseyin. "An Enumerative-Probabilistic Study of Chord Diagrams." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1373310487.
Full text
15
Ash, Patricia. "Dominating cycles, Hamilton cycles and cycles with many chords in 2-connected graphs." Thesis, Goldsmiths College (University of London), 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.490379.
Full text
16
Arredondo, Ryan. "Properties of Graphs Used to Model DNA Recombination." Scholar Commons, 2014. https://scholarcommons.usf.edu/etd/4979.
Full textAbstract:
A model for DNA recombination uses 4-valent rigid vertex graphs,
called assembly graphs. An assembly graph,
similarly to the projection of knots, can be associated with an
unsigned Gauss code, or double occurrence word.
We define biologically motivated reductions that act on double
occurrence words and, in turn, on their associated assembly graphs. For
every double occurrence word w there is a sequence of reduction
operations that may be applied to w so that what remains is the
empty word, [epsilon]. Then the nesting index of a word w,
denoted by NI(w), is defined to to be the least number of reduction
operations necessary to reduce w to [epsilon]. The nesting index
is the first property of assembly graphs that we study. We use chord
diagrams as tools in our study of the nesting index. We observe two
double occurrence words that correspond to the same circle graph,
but that have arbitrarily large differences in nesting index values.
In 2012, Buck et al. considered the cellular
embeddings of assembly graphs into orientable surfaces. The genus
range of an assembly graph [Gamma], denoted gr([Gamma]), was defined to
be the set of integers g where g is the genus of an orientable
surface F into which [Gamma] cellularly embeds. The genus range is
the second property of assembly graphs that we study. We generalize
the notion of the genus range to that of the genus spectrum, where
for each g [isin] gr([Gamma]) we consider the number of orientable
surfaces F obtained from [Gamma] by a special construction, called a
ribbon graph construction, that have genus g. By
considering this more general notion we gain a better understanding
of the genus range property. Lastly, we show how one can obtain the
genus spectrum of a double occurrence word from the genus spectrums
of its irreducible parts, i.e., its double occurrence subwords.
In the final chapter we consider constructions of double occurrence
words that recognize certain values for nesting index and genus
range. In general, we find that for arbitrary values of nesting index
[ge] 2 and genus range, there is a double occurrence word that
recognizes those values.
17
Xu, Binbin. "L'identité de Pleijel hyperbolique, la métrique de pression et l'extension centrale du groupe modulaire via quantification de Chekhov-Fock." Thesis, Grenoble, 2014. http://www.theses.fr/2014GRENM068/document.
Full textAbstract:
Cette thèse consiste en trois parties que j'ai faites pendant ces trois ans.La première partie va être constituée de l'étude de la distribution de la longueur de corde sur le plan hyperbolique. Nous montrons l'identité de Pleijel pour le plan hyperbolique. En utilisant cette identité, nous remontrons l'identité de formule de Crofton et l'inégalité isopérimétrique pour le plan hyperbolique, et puis nous calculons la distribution de la longueur de corde associée à un triangle idéal et celle associée à un quadrilatère idéal. Ensuit, nous montons les résultats analogues pour les surfaces riemannienne simplement connexes avec la courbure constante. La seconde partie va contribuer aux études de la métrique de pression sur l'espace de Teichmüller d'un tore privé d'un disque. En étudiant la dégénération du tore quand la longueur du bord va à l'infini, nous trouvons la relation de cette métrique avec la métrique de pression sur l'espace modulaires des graphes métriques. Nous montrons ensuite que la fonction de l'entropie n'est pas constante sur les feuilles symplectique de l'espace Teichmüller d'une surface à bord.Finalement, la troisième partie concerne la quantification de l'espace de Teichmüller d'une surface avec les piqûres. nous montrons. Dans ce chapitre, nous étudions l'extension centrale du groupe modulaire via la quantification de Chekhov-Fock et calculons sa classe de cohomologie qui est 12 fois la classe de Meyer plus les classes d'Euler associées aux piqûresThis thesis consists of three parts corresponding to the three subjects that I have studied during the last three years.The first part contains the study of the chord length distribution associated to a compact (or non-compact) domain in the hyperbolic plane. We prove the hyperbolic Pleijel identity. By using this identity, we find new approaches to the Crofton's formula and the isoperimetric inequality, and then compute the chord length distribution associated to an ideal triangle and that associated to an ideal quadrilateral. Then we prove the analogue results for the simply connected Riemannian surface with constant curvature.The second part of this thesis (Chapter 5) consists of the study of the pressuremetric on the Teichmüller space of one-holed torus. By studying the degeneration of the torus when the boundary length goes to infinity, we find the relation of this metric to the pressure metric on the moduli space of metric graphs. Then we study the entropy function and prove that it is not constant on the symplectic leaf of the Teichmüller space of a bordered surface.Finally, the third part concerns the quantization of the Teichmüller space of a punctured surface. In this chapter, we study the central extension of the mapping class group coming from the quantization and compute its cohomology class which is 12 times the Meyer class plus the Euler classes associated to punctures
18
Golz, Marcel. "Parametric quantum electrodynamics." Doctoral thesis, Humboldt-Universität zu Berlin, 2019. http://dx.doi.org/10.18452/19776.
Full textAbstract:
In dieser Dissertation geht es um Schwinger-parametrische Feynmanintegrale in der Quantenelektrodynamik. Mittels einer Vielzahl von Methoden aus der Kombinatorik und Graphentheorie wird eine signifikante Vereinfachung des Integranden erreicht. Nach einer größtenteils in sich geschlossenen Einführung zu Feynmangraphen und -integralen wird die Herleitung der Schwinger-parametrischen Darstellung aus den klassischen Impulsraumintegralen ausführlich erläutert, sowohl für skalare Theorien als auch Quantenelektrodynamik. Es stellt sich heraus, dass die Ableitungen, die benötigt werden um Integrale aus der Quantenelektrodynamik in ihrer parametrischen Version zu formulieren, neue Graphpolynome enthalten, die auf Zykeln und minimalen Schnitten (engl. "bonds") basieren. Danach wird die Tensorstruktur der Quantenelektrodynamik, bestehend aus Dirac-Matrizen und ihren Spuren, durch eine diagrammatische Interpretation ihrer Kontraktion zu ganzzahligen Faktoren reduziert. Dabei werden insbesondere gefärbte Sehnendiagramme benutzt. Dies liefert einen parametrischen Integranden, der über bestimmte Teilmengen solcher Diagramme summierte Produkte von Zykel- und Bondpolynomen enthält. Weitere Untersuchungen der im Integranden auftauchenden Polynome decken Verbindungen zu Dodgson- und Spannwaldpolynomen auf. Dies wird benutzt um eine Identität zu beweisen, mit der sehr große Summen von Sehnendiagrammen in einer kurzen Form ausgedrückt werden können. Insbesondere führt dies zu Aufhebungen, die den Integranden massiv vereinfachen.This thesis is concerned with the study of Schwinger parametric Feynman integrals in quantum electrodynamics. Using a variety of tools from combinatorics and graph theory, significant simplification of the integrand is achieved. After a largely self-contained introduction to Feynman graphs and integrals, the derivation of the Schwinger parametric representation from the standard momentum space integrals is reviewed in full detail for both scalar theories and quantum electrodynamics. The derivatives needed to express Feynman integrals in quantum electrodynamics in their parametric version are found to contain new types of graph polynomials based on cycle and bond subgraphs. Then the tensor structure of quantum electrodynamics, products of Dirac matrices and their traces, is reduced to integer factors with a diagrammatic interpretation of their contraction. Specifically, chord diagrams with a particular colouring are used. This results in a parametric integrand that contains sums of products of cycle and bond polynomials over certain subsets of such chord diagrams. Further study of the polynomials occurring in the integrand reveals connections to other well-known graph polynomials, the Dodgson and spanning forest polynomials. This is used to prove an identity that expresses some of the very large sums over chord diagrams in a very concise form. In particular, this leads to cancellations that massively simplify the integrand.
19
HE, JIN-WEN, and 何錦文. "Fast parallel algorithms related to chordal graph." Thesis, 1988. http://ndltd.ncl.edu.tw/handle/66639018202847950320.
Full textAbstract:
博士國立清華大學
計算機管理決策研究所
76
Chordal graph 與相當多的問題有很大的關連，尤其是有關解疏散式線性方程組的問 題。在本篇博士論文裹，我們提出若干快速平行計算方法來解一些與 Chordal graph 有關的問題。這些問題可分成兩個部分。第一個部分是直接與Chordal graph 有關的 問題。這部分的問題包括認定Chordal graph 的問題及在Chordal graph 上找一些特 定的事物，這些事物包括maximal clique，clique true ，minimum coloring，及pe rfect elimination scheme。我們的做法比起以前人的做法有很大的改進。我們把解 這些問題所需的處理器個數從０（ n）或０（ n）降到０（ n），並且把所需 的計算時間從０（logn）降到０（logn），其中n 是代表頂點的個數。我們第二部 分解的問題是解疏散式三角線性方程組。我們提出兩個平行計算方法來解這個問題。 這兩個方法都比前人的解法快很多。第一個方法是解一般的疏散式三角線性方程組。 一些模擬的結果顯示這個方法的執行時間隨給定方程組的疏散性而改變。第二個方法 ，利用第一個方法當副程式，是用來解一些特定的疏散線性方程組，這些方程組的係 數矩陣是得自某一對稱矩陣的LU分解。我們應用很多Chordal graph 的特性來設計第 二個計算方法並分析這兩個計算方法的執行效率。
20
"Linear time algorithms for graphs close to chordal graphs." 2003. http://library.cuhk.edu.hk/record=b5891620.
Full textAbstract:
Ho Man Lam.Thesis (M.Phil.)--Chinese University of Hong Kong, 2003.
Includes bibliographical references (leaves 51-54).
Abstracts in English and Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Statement of problems --- p.1
Chapter 1.2 --- Notation and definitions --- p.3
Chapter 1.3 --- Graph families --- p.4
Chapter 1.4 --- Related work --- p.5
Chapter 1.4.1 --- Graph modification problems --- p.5
Chapter 1.4.2 --- Independent set --- p.6
Chapter 1.5 --- Overview of the thesis --- p.7
Chapter 2 --- Recognition of Nearly Chordal Graphs --- p.8
Chapter 2.1 --- Critical edges not in triangles --- p.9
Chapter 2.2 --- Critical edges in triangles --- p.10
Chapter 2.3 --- A linear time algorithm --- p.13
Chapter 3 --- Recognition of Almost Chordal Graphs --- p.15
Chapter 3.1 --- Minimal separator --- p.16
Chapter 3.2 --- "All chordless cycles passing through the minimal (x, z)-separator S" --- p.18
Chapter 3.3 --- Algorithm for almost chordal graphs recognition --- p.22
Chapter 3.4 --- Another approach to find a critical vertex if all chordless cycles pass through S --- p.26
Chapter 3.5 --- A linear algorithm for all chordless cycles passing through S --- p.28
Chapter 4 --- Maximum Independent Bases of Chordal Graphs --- p.32
Chapter 4.1 --- Maximum independent base --- p.32
Chapter 4.1.1 --- Finding a maximum independent set of a chordal graph . --- p.33
Chapter 4.1.2 --- Another approach to prove the algorithm --- p.33
Chapter 4.1.3 --- Maximum independent base --- p.34
Chapter 4.1.4 --- Vertices in the maximum independent base --- p.36
Chapter 4.1.5 --- A linear time algorithm --- p.38
Chapter 4.2 --- Generating all maximum independent sets --- p.39
Chapter 4.2.1 --- Relation between two maximum independent sets --- p.39
Chapter 4.2.2 --- Algorithm --- p.40
Chapter 4.3 --- Maximum induced split graph of a chordal graph --- p.43
Chapter 4.3.1 --- Property of maximum induced split subgraph --- p.44
Chapter 4.3.2 --- A linear time algorithm --- p.45
Chapter 5 --- Concluding Remarks --- p.48
Chapter 5.1 --- Summary of results --- p.48
Chapter 5.2 --- Open problems --- p.48
Bibliography --- p.51
21
Klem, Estiaan Murrell. "Non-chordal patterns associated with the positive definite completion problem / Estiaan Murrell Klem." Thesis, 2015. http://hdl.handle.net/10394/15334.
Full textAbstract:
A partial matrix, is a matrix for which some entries are specified and some unspecified.
In general completion problems ask whether a given partial matrix, may be completed to
a matrix where all the entries are specified, such that this completion admits a specific
structure. The positive definite completion problem asks whether a partial Hermitian
matrix admits a completion such that the completed matrix is positive semidefinite.
The minimum solution criterion, is that every fully specified principal submatrix is nonnegative.
Then the set of partial Hermitian matrices, which admit a positive semidefinite
completion, forms a convex cone, and its dual cone can be identified as the set of positive
semidefinite Hermitian matrices with zeros in the entries that correspond to non-edges in
the graph G: Furthermore, the set of partial Hermitian matrices, with non-negative fully
specified principal minors, also forms a convex cone, and its dual cone can be identified as
the set of positive semidefinite Hermitian matrices which can be written as the sum of rank
one matrices, with underlying graph G. Consequently, the problem reduces to determining
when these cones are equal. Indeed, we find that this happens if and only if the underlying
graph is chordal. It then follows that the extreme rays of the cone of positive semidefinite
Hermitian matrices with zeros in the entries that correspond to non-edges in the graph
G is generated by rank one matrices. The question that arises, is what happens if the
underlying graph is not chordal. In particular, what can be said about the extreme rays of
the cone of positive semidefinite matrices with some non-chordal pattern. This gives rise
to the notion of the sparsity order of a graph G; that is, the maximum rank of matrices
lying on extreme rays of the cone of positive semidefinite Hermitian matrices with zeros
in the entries that correspond to non-edges in the graph G: We will see that those graphs
having sparsity order less than or equal to 2 can be fully characterized. Moreover, one can
determine in polynomial time whether a graph has sparsity order less than or equal to 2,
using a clique-sum decomposition. We also show that one can determine whether a graph
has sparsity order less than or equal to 2, by considering the characteristic polynomial of
the adjacency matrix of certain forbidden induced subgraphs and comparing it with the
characteristic polynomial of principal submatrices of appropriate size.MSc (Mathematics), North-West University, Potchefstroom Campus, 2015
22
Yang, Feiran. "New results on broadcast domination and multipacking." Thesis, 2015. http://hdl.handle.net/1828/6627.
Full textAbstract:
Let G be a graph and f be a function that maps V to {0,1,2, ..., diam(G)}.
Let V+ be the set of all vertices such that f(v) is positive.
If for every vertex v not in V+ there exists a vertex w in V+ such that
the distance between v and w is at most f(w),
then f is called a dominating broadcast of G.
The cost of the broadcast f is the sum of the values f(v) over all vertices v in V.
The minimum cost of a dominating broadcast is called the broadcast domination number of G.
A subset S of V is a multipacking if, for every v in V and for every integer k which is at least 1 and at most rad(G),
the set S contains at most k vertices at distance at most k from v.
The multipacking number of G is the maximum cardinality of a multipacking of G.
In the first part of the thesis, we describe how linear programming can be used to give a cubic algorithm to find the broadcast domination number and multipacking number of strongly chordal graphs.
Next, we restrict attention to trees, and describe linear time algorithms to compute these numbers. Finally, we introduce k-broadcast domination and k-multipacking, develop the basic theory and give a bound for the 2-broadcast domination number of a tree in terms of its order.Graduate
23
Jampani, Krishnam Raju. "Simultaneous Graph Representation Problems." Thesis, 2011. http://hdl.handle.net/10012/5793.
Full textAbstract:
Many graphs arising in practice can be represented in a concise and intuitive way that conveys their structure. For example: A planar graph can be represented in the plane with points for vertices and non-crossing curves for edges. An interval graph can be represented on the real line with intervals for vertices and intersection of intervals representing edges. The concept of ``simultaneity'' applies for several types of graphs: the idea is to find representations for two graphs that share some common vertices and edges, and ensure that the common vertices and edges are represented the same way. Simultaneous representation problems arise in any situation where two related graphs should be represented consistently. A main instance is for temporal relationships, where an old graph and a new graph share some common parts. Pairs of related graphs arise in many other situations. For example, two social networks that share some members; two schedules that share some events, overlap graphs of DNA fragments of two similar organisms, circuit graphs of two adjacent layers on a computer chip etc. In this thesis, we study the simultaneous
representation problem for several graph classes.
For planar graphs the problem is defined as follows. Let G1 and G2 be two graphs sharing some vertices and edges. The simultaneous planar embedding problem asks whether there exist planar embeddings (or drawings) for G1 and G2 such that every vertex shared by the two graphs is mapped to the same point and every shared edge is mapped to the same curve in both embeddings. Over the last few years there has been a lot of work on simultaneous planar embeddings, which have been called `simultaneous embeddings with fixed edges'. A major open question is whether simultaneous planarity for two graphs can be tested in polynomial time. We give a linear-time algorithm for testing the simultaneous planarity of any two graphs that share a 2-connected subgraph. Our algorithm also extends to the case of k planar graphs, where each vertex [edge] is either common to all graphs
or belongs to exactly one of them.
Next we introduce a new notion of simultaneity for intersection graph classes (interval graphs, chordal graphs etc.) and for comparability graphs. For interval graphs, the problem is defined as follows. Let G1 and G2 be two interval graphs sharing some vertices I and the edges induced by I. G1 and G2 are said to be `simultaneous interval graphs' if there exist interval representations of G1 and G2 such that any vertex of I is assigned to the same interval in both the representations. The `simultaneous representation problem' for interval graphs asks whether G1 and G2 are simultaneous interval graphs. The problem is defined in a similar way for other intersection graph classes.
For comparability graphs and any intersection graph class, we show that the simultaneous representation problem for the graph class is equivalent to a graph augmentation problem: given graphs G1 and G2, sharing vertices I and the corresponding induced edges, do there exist edges E' between G1-I and G2-I such that the graph G1 U G_2 U E' belongs to the graph class. This equivalence implies that the simultaneous representation problem is closely related to other well-studied classes in the literature, namely, sandwich graphs and probe graphs.
We give efficient algorithms for solving the simultaneous representation problem for interval graphs, chordal graphs, comparability graphs and permutation graphs. Further, our algorithms for comparability and permutation graphs solve a more general version of the problem when there are multiple graphs, any two of which share the same common graph. This version of the problem also generalizes probe graphs.
24
Chiang, Wei-Ling, and 江韋伶. "A Linear Time Algorithm for the Simple Moplex Ordering of a Strongly Chordal Graph." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/26826356427901784124.
Full textAbstract:
碩士國立臺北商業技術學院
資訊與決策科學研究所
102
Berry [A. Berry, J. P. Bordat, Moplex elimination orderings, Electronic Notes in Discrete Mathematics, 8 (2001) 6--9] proved that a graph G is choral if and only if G admits a moplex ordering. In this thesis, we also prove that a strongly chordal graph has a similar ordering namely simple moplex ordering. Then, we propose an algorithm that can be run in linear time to find such an ordering.
25
Connon, Emma. "Generalizing Fröberg's Theorem on Ideals with Linear Resolutions." 2013. http://hdl.handle.net/10222/38565.
Full textAbstract:
In 1990, Fröberg presented a combinatorial classification of the quadratic square-free monomial ideals with linear resolutions. He showed that the edge ideal of a graph has a linear resolution if and only if the complement of the graph is chordal. Since then, a generalization of Fröberg's theorem to higher dimensions has been sought in order to classify all square-free monomial ideals with linear resolutions. Such a characterization would also give a description of all square-free monomial ideals which are Cohen-Macaulay.
In this thesis we explore one method of extending Fröberg's result. We generalize the idea of a chordal graph to simplicial complexes and use simplicial homology as a bridge between this combinatorial notion and the algebraic concept of a linear resolution. We are able to give a generalization of one direction of Fröberg's theorem and, in investigating the converse direction, find a necessary and sufficient combinatorial condition for a square-free monomial ideal to have a linear resolution over fields of characteristic 2.
26
Chen, Jan-Hau, and 陳建豪. "Relations of Chordal Probe Graphs and Tolerance Graphs." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/87804271940117392669.
Full textAbstract:
碩士國立臺灣海洋大學
資訊工程學系
93
Tolerance graphs arise from the intersection of intervals with varying tolerances in a way that generalizes both interval graphs and permutation graphs. In this paper we discuss the subclasses of tolerance graphs, interval probe graphs, and chordal probe graphs. We show that G is chordal graph without T3 or , then G is an interval probe graph if and only if G is a tolerance graph. We also introduce the class of chordal probe graphs which are a generalization of both interval probe graphs and chord graphs.
27
Lai, Yu-Ren, and 賴育仁. "Some Problems on Chordal Probe Graphs." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/25771468419118238317.
Full text
28
Wu, Wu-Hsiung, and 吳武雄. "L(2,1)-labeling on Chordal Graphs." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/06413108054791405000.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
91
For a general graph $G=(V,E)$, an {\bf $L$(2, 1)-$labeling$} of $G$ is a function $f$ from the vertex set $V$ to the set of nonnegative integers such that $|f(x)-f(y)|\geq 2$ if $d(x,y)=1$ and $|f(x)-f(y)|\geq 1$ if $d(x, y)=2$, where $d(x, y)$ is the minimum length of a path between $x$ and $y$ in $G$, called the distance between $x$ and $y$. A $k$-$L$(2, 1)-$labeling$ is an $L$(2, 1)-$labeling$ such that no label is greater than $k$. The $L$(2, 1)-$labeling$ $number$ of $G$, denoted by $\lambda(G)$, is the smallest number $k$ such that $G$ has a $k$-$L$(2,1)-$labeling$. The $L$(2, 1)-$labeling$ problem has been extensively studied during the past ten years. These include bounds for general graphs as well as special graphs such as trees, chordal graphs, strongly chordal graphs; exact values for paths, cycles, etc. In this paper, we focus on the $L$(2, 1)-$labeling$ problem on chordal graphs. Sakai \cite{SAK94} showed that $\lambda(G) \leq \frac{(\Delta + 3)^2}{4}$ for any chordal graph $G$ with maximum degree $\Delta$. We improve this bound to $\frac{\Delta^2}{4} + 6$.
29
Chang, Yu-Wei, and 張育瑋. "The 2-center problem in chordal graphs." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/78683245220635657035.
Full textAbstract:
碩士國立臺北商業技術學院
資訊與決策科學研究所
100
In a graph G, the p-center problem is to identify p vertices of G for locating some kind of facilities such that the maximum among the distances from all vertices to their nearest facility is minimized. In this thesis, we propose an O(n)-time algorithm for computing a 2-center in a chordal graph with maximum degree at most three, where a graph is chordal if every induced cycle of length at least four has a chord, and n is the number of vertices in the graph.
30
戴昆成. "Some Problems on Weakly Chordal Graphs, co-Perfect Orderable Graphs and Alternately Orientable Graphs." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/52490934450689952121.
Full text
31
Hsu, Chung Chang, and 徐忠長. "On Two Location Problems in Strongly Chordal Graphs." Thesis, 1993. http://ndltd.ncl.edu.tw/handle/00511923535022306480.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
81
Given a simple graph G, which is composed of the set of vertices V and the set of edges E, a set of vertices D is a dominating set if every vertex in V is adjacent to at least one vvertex in D. In this thesis, we define two terms related to the dominating set. One is k-fault tolerant dominating set which is a set D of V such that the cardinality of the intersection of D and the close neighborhood of v is greater than k for every v in V. The other is minimum h-disjoint dominating set problem which is to find a minimum h-disjoint dominating set such that each vertex in V is adjacent to at least h vertices in this set. Then, we partititon the set into h disjoint sets, and each set is a dominating set. In this thesis, a linear time algorithm is proposed to solve the k- fault tolerant dominating set problem and the minimum h- disjoint dominating set problem on strongly chordal graphs when the strong elimination ordering is given and another linear time algorithm is used to partition this set into h disjoint sets. As a byproduct, we will show strongly chordal graphs to be domatically perfect which is new-defined. Further, we relax the disjointness of these dominating sets. An linear time algorithm is found to derive the minimum cardinality of the two minimum dominating sets on, the subclasses of strongly chordal graphs, interval graphs.
32
Chu, Kuan-Ting, and 褚冠廷. "Mutual Transferability of Dominating Sets in Strongly Chordal Graphs and Cactus Graphs." Thesis, 2018. http://ndltd.ncl.edu.tw/handle/4td2ug.
Full text
33
Chen, Ya-Mei, and 陳雅玫. "The Fault Tolerant Domination Problem on Strongly Chordal Graphs." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/89509799514631971665.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
89
Given a graph G = (V, E) and a fault tolerant function f from V to N, a dominating set D(subset of V) is fault tolerant if | D∩N[v] | >= f(v) for all v in V. Given a graph G = (V, E) and a function g,from V to integers, the weight of g is defined as w(g) =Σ(v in V) g(v). For a vertex v in V, let g[v] =Σ(u in N[v]) g(u). A signed dominating function of G is a function g,from V to {-1,1}, such that g[v] >= 1 for all v in V. The signed domination number rs(G)(gamma_s(G)) of G is the minimum weight of a signed dominating function on G. We call a signed dominating function of a weight rs(G) as a rs-function of G. The signed domination problem is to find a rs-function of a graph. In this paper, we propose a new concept, fault tolerant domination. It is a generalization of some kinds of domination problems. Furthermore, we give an O(n + m) time algorithm to find a fault tolerant dominating set of minimum cardinality of a given strongly chordal graph G and a fault tolerant function f of G.
34
Tsay, Ming Shiann, and 蔡明憲. "Efficient Algorithms for Some Problems on Subclasses of Chordal Graphs." Thesis, 1994. http://ndltd.ncl.edu.tw/handle/25117474535146377267.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
82
Two problems are discussed in this thesis. One is the all pairs shortest paths problem, and the other is the minimum weight k dominating sets problem. The all pairs shortest paths problem is applied extensively. In the past, scholars paid attention to reducing the time complexity of solving such problem on general graphs. They achieved .OMICRON.(n^3) time complexity in worst case, and .OMICRON.(n^2log n) time complexity in average case. When we restrict the problem to being solved on some special graphs, the optimal algorithm with time complexity .OMICRON.( n^2) can be found. In this thesis, the problem is discussed on chordal graphs and on strongly chordal graphs. We apply the result to reduce the time complexities of solving the k- domination problem, the k-stability problem, the k-domatic partition problem, and the k-coloring problem. The minimum weight k dominating sets problem is an extension of the domination problem. The domination problem is NP-complete on general graphs, so is the minimum weight k dominating sets problem. Fortunately, on interval graphs, we can transform the minimum weight k dominating sets problem into the minimum cost network flow problem with flow .absolute.(f)=k. The idea is from the algorithm for solving the maximum k-covering problem on transitive graphs proposed by Sarrafzadeh and Lou. The minimum cost network flow problem can be solved in .OMICRON.( km) time by the algorithm designed by Edmonds and Karp, if all the costs are nonnegative. We apply the algorithm to solve the minimum weight k dominating sets problem in .OMICRON.(kn^2) time even the costs are negative.
35
Tsai, Yun-Cheng, and 蔡芸琤. "Some Results On Bounded Tolerance, Cocomparability, And Weakly Chordal Graphs." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/60041434999721557614.
Full textAbstract:
碩士國立臺灣海洋大學
資訊工程學系
93
Tolerance graphs were first introduced by Golumbic [1] in 1984, which generalize both interval and permutation graphs with a lot of applications. The main theorem is: A tolerance graph is bounded, and then it is a cocomparability graph. However the converse of the theorem is still unsolved so far. We give a complete of proof of that by using Knotting graph [3] that is: A tolerance graph is a cocomparability graph then it is bounded. With some related topic, we also prove that a weakly chordal graph which is AT-free and a comparability graph, then it is a permutation graph. Finally we construct a hierarchy of classes of the related graphs and give some separating examples.
36
Chen, Yi Hua, and 陳怡華. "Algorithmic Aspects of the Generalized Clique-Transversal Set on Chordal Graphs." Thesis, 1993. http://ndltd.ncl.edu.tw/handle/27300462804839335443.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
81
Given a graph G = (V, E), a set T is called a clique- transversal set if absolute (T intersection C) .gsidm. 1 for every clique C in G, and define the clique-transversal number as the minimum cardinality of a clique-transversal set. The clique-transversal problem is to determine the clique- transversal number. More, if each clique is associated with an integer, then we can generalize the clique-transversal set to the generalized clique-transversal set, that is, T is a generalized clique-transversal set if absolute(T intersection Ci) .gsidm. ri for every clique Ci in G. Hence the generalized clique-transversal problem is, given a graph G =(V ,E) and a relation R = .lbrace.(Ci, ri).rbrace., to determine the minimum cardinality of a generalized clique-transversal set, called the generalized clique-transversal number with respect to R. We first give an efficient algorithm for the generalized clique- transversal problem on strongly chordal graphs. And then show the NP-completeness of the clique-transversal problem on the undirected path graphs and k-trees. Hence the generalized clique -transversal problem is NP-complete on undirected path graphs and k-trees, since the clique-transversl problem is a special case of the generalized clique-transversal problem. More, the generalized clique-transversal problem has some clique-related problems -- the maximum q-colorable subgraph, the generalized vertex covering and the neighborhood-covering problems. This problems can be done easily as the generalized clique-transversal problem has solved. We also consider the algorithmic complexity of these problems an all graphs mentioned above.
37
Chiu, Guei-Lin, and 邱圭琳. "A Certifying Algorithm for Finding Hinge Vertices of Strongly Chordal Graphs." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/36469603676772326548.
Full textAbstract:
碩士國立暨南國際大學
資訊工程學系
96
Let G = (V, E) be a graph, and let G−u be the subgraph of G induced by the vertex set V(G) − {u}. A vertex u ∈ V(G) is said to be a hinge vertex of G if and only if there exist two vertices x, y ∈ V(G − u) such that dG−u(x, y) > dG(x, y), where dG(x , y) is the distance (i.e., the length of a shortest path) between x and y in G. A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence proving that the answer has not been compromised by a bug in the implementation. In this paper, we present an Ο(n + m) time certifying algorithm for finding all hinge vertices of strongly chordal graphs.
38
Ding, Kun-Fu, and 丁坤福. "Some Results of Incidence Coloring on Generalized Petersen Graphs and Chordal Rings." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/44656311289030408998.
Full textAbstract:
碩士明志科技大學
工業工程與管理系碩士班
103
An incidence of G is a pair (v, e) where v ∈ V(G) is a vertex and e ∈ E(G) is an edge incident with v. Two incidences (v, e) and (w, f) are adjacent if one of the following holds: (a) v = w, (b) e = f or (c) vw = e or vw = f. Let I(G) be the set consisting of all incidences of a graph G. A proper incidence coloring of G is a mapping from I(G) to a set of colors such that adjacent incidences are assigned distinct colors. The smallest number of colors required for such a coloring is called the incidence coloring number of G, and is denoted by χi(G). In this paper, we study the incidence coloring on generalized Petersen graphs GP(n, k) and Chordal Rings CR(N, d). We first assure that 4 ≤ χi(GP(n, k)) ≤ 5. Furthermore, we provide the following results: (i) χi(GP(n, k)) = 5 if n is odd, (ii) χi(GP(n, 2)) = 5, and (iii) χi(GP(n, k)) = 4 if n ≡ 0 (mod 4) and k is odd. Then, we have the following results on χi(CR(N, d)): (i) χi(CR(N, d)) = 5, if N ≡ 0 (mod 5) and d = 2 or 3, (ii) χi(CR(N, 2)) = 6, if N mod 5 ≠ 0, and (iii) χi(CR(N, 3)) = 6, if N ≡ 2 (mod 5).
39
Mathew, Rogers. "Boxicity And Cubicity : A Study On Special Classes Of Graphs." Thesis, 2012. http://etd.iisc.ernet.in/handle/2005/2320.
Full textAbstract:
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 degree.
5. Boxicity of a k-leaf power is at most k -1. For every k, there exist k-leaf powers whose boxicity is exactly k - 1. Since leaf powers are a subclass of strongly chordal graphs, this result implies that there exist strongly chordal graphs with arbitrarily high boxicity
6. Otachi et al. [8] conjectured that chordal bipartite graphs (CBGs) have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of CBGs that have unbounded boxicity. We first prove that the bipartite power of a tree (which is a CBG) is a CBG and then show that there exist trees whose bipartite powers have high boxicity. Later in Chapter ??, we prove a more generic result in bipartite powering. We prove that, for every k ≥ 3, the bipartite power of a bipartite, k-chordal graph is bipartite and k-chordal thus implying that CBGs are closed under bipartite powering.
7. Boxicity of a line graph with maximum degree Δ is O(Δ log2 log2 Δ). This is a log2 Δ
log log Δ
factor improvement over the best known upper bound for boxicity of any graph [1]. We also prove a non-trivial lower bound for the boxicity of a d-dimensional hypercube.
40
Lin, Cheng-Ying, and 林政瑩. "An O(n3)-Time Algorithm for Minimum Fill-in Problem on Chordal Bipartite Graphs." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/20166405857904142646.
Full textAbstract:
碩士國立中正大學
資訊工程所
95
A graph is a chordal bipartite graph if it is bipartite and every cycle greater than four has a chord. For an arbitrary graph, a minimum fill-in of G refers to a minimum cardinality set E’ from Ē = {(u, v) E : u, v ∈ V } such that G = (V,E ∪E’) is chordal. Given a graph G = (V, E) and a subset X of V , G[X] is called an induced cycle of length l, denoted by Cl, if G[X] is a cycle and its length is l. For a graph G = (V,E), and a set E’ from Ē = {(u, v) E : u ∈ V and v ∈ V } is said to be a C4-destroying set if for every induced cycle (w, x, y, z,w) of length four in G, the edge (w, y) or (x, z) is in E’. Chang proved that for a chordal bipartite G = (S, T,E) and E’ be a minimum C4-destroying set of G, G’ = (S ∪ T,E ∪ E’) is a chordal graph. In this paper, we show that the minimum C4-destroying set of a chordal bipartite graph can be found in O(n3) time. Therefore the minimum fill-in problem on chordal bipartite graphs can be solved in O(n3) time.
41
"Erdos--Ko--Rado Theorems: New Generalizations, Stability Analysis and Chvatal's Conjecture." Doctoral diss., 2011. http://hdl.handle.net/2286/R.I.8895.
Full textAbstract:
abstract: The primary focus of this dissertation lies in extremal combinatorics, in particular intersection theorems in finite set theory. A seminal result in the area is the theorem of Erdos, Ko and Rado which finds the upper bound on the size of an intersecting family of subsets of an n-element set and characterizes the structure of families which attain this upper bound. A major portion of this dissertation focuses on a recent generalization of the Erdos--Ko--Rado theorem which considers intersecting families of independent sets in graphs. An intersection theorem is proved for a large class of graphs, namely chordal graphs which satisfy an additional condition and similar problems are considered for trees, bipartite graphs and other special classes. A similar extension is also formulated for cross-intersecting families and results are proved for chordal graphs and cycles. A well-known generalization of the EKR theorem for k-wise intersecting families due to Frankl is also considered. A stability version of Frankl's theorem is proved, which provides additional structural information about k-wise intersecting families which have size close to the maximum upper bound. A graph-theoretic generalization of Frankl's theorem is also formulated and proved for perfect matching graphs. Finally, a long-standing conjecture of Chvatal regarding structure of maximum intersecting families in hereditary systems is considered. An intersection theorem is proved for hereditary families which have rank 3 using a powerful tool of Erdos and Rado which is called the Sunflower Lemma.Dissertation/Thesis
Ph.D. Mathematics 2011