Results 11 to 20 of about 1,930 (230)
Edge erasures and chordal graphs
Electronic Journal of Graph Theory and Applications, 2021 We prove several results about chordal graphs and weighted chordal graphs by focusing on exposed edges. These are edges that are properly contained in a single maximal complete subgraph.
Jared Culbertson +2 more
doaj +1 more source
Axiomatic characterizations of Ptolemaic and chordal graphs [PDF]
Opuscula Mathematica, 2023 The interval function and the induced path function are two well studied class of set functions of a connected graph having interesting properties and applications to convexity, metric graph theory. Both these functions can be framed as special instances
Manoj Changat +2 more
doaj +1 more source
Further results on Hendry's Conjecture [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Recently, a conjecture due to Hendry was disproved which stated that every Hamiltonian chordal graph is cycle extendible. Here we further explore the conjecture, showing that it fails to hold even when a number of extra conditions are imposed.
Manuel Lafond +2 more
doaj +1 more source
A Short Proof of the Size of Edge-Extremal Chordal Graphs
Journal of Mathematical Sciences and Modelling, 2022 [3] have recently determined the maximum number of edges of a chordal graph with a maximum degree less than $d$ and the matching number at most $\nu$ by exhibiting a family of chordal graphs achieving this bound. We provide simple proof of their result.
Mordechai Shalom
doaj +1 more source
Semipaired Domination in Some Subclasses of Chordal Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 A dominating set $D$ of a graph $G$ without isolated vertices is called semipaired dominating set if $D$ can be partitioned into $2$-element subsets such that the vertices in each set are at distance at most $2$. The semipaired domination number, denoted
Michael A. Henning +2 more
doaj +1 more source
Efficient (j, k)-Dominating Functions
Discussiones Mathematicae Graph Theory, 2023 For positive integers j and k, an efficient (j, k)-dominating function of a graph G = (V, E) is a function f : V → {0, 1, 2, . . ., j} such that the sum of function values in the closed neighbourhood of every vertex equals k. The relationship between the
Klostermeyer William F. +3 more
doaj +1 more source
On the End-Vertex Problem of Graph Searches [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 End vertices of graph searches can exhibit strong structural properties and are crucial for many graph algorithms. The problem of deciding whether a given vertex of a graph is an end-vertex of a particular search was first introduced by Corneil, K\"ohler
Jesse Beisegel +6 more
doaj +1 more source
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs [PDF]
Journal of Combinatorial Optimization, 2012 A k-colouring of a graph G=(V,E) is a mapping c:V?{1,2,?,k} such that c(u)?c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if they differ in colour on just one vertex of G. We introduce a class of k-colourable graphs, which we call
Bonamy, M. +4 more
openaire +5 more sources
Discrete Mathematics & Theoretical Computer Science, 2019 Slimness of a graph measures the local deviation of its metric from a tree metric. In a graph $G=(V,E)$, a geodesic triangle $\bigtriangleup(x,y,z)$ with $x, y, z\in V$ is the union $P(x,y) \cup P(x,z) \cup P(y,z)$ of three shortest paths connecting ...
Feodor F. Dragan, Abdulhakeem Mohammed
doaj +1 more source
Characterizing 2-Trees Relative to Chordal and Series-Parallel Graphs
Theory and Applications of Graphs, 2021 The 2-connected 2-tree graphs are defined as being constructible from a single 3-cycle by recursively appending new degree-2 vertices so as to form 3-cycles that have unique edges in common with the existing graph.
Terry McKee
doaj +1 more source