Log in

Relevant bibliographies by topics / Chordal graph / Journal articles

To see the other types of publications on this topic, follow the link: Chordal graph.

Journal articles on the topic 'Chordal graph'

Author: Grafiati

Published: 4 June 2021

Last updated: 25 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles 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 journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Jeya Jothi, R. Mary, and A. Amutha. "Characterization of Super Strongly Perfect Graphs in Chordal and Strongly Chordal Graphs." Mapana - Journal of Sciences 11, no. 4 (2012): 121–31. http://dx.doi.org/10.12723/mjs.23.10.

Full text

Abstract:

A Graph G is Super Strongly Perfect Graph if every induced sub graph H of G possesses a minimal dominating set that meets all the maximal complete sub graphs of H. In this paper, we have investigated the characterization of Super Strongly Perfect graphs using odd cycles. We have given the characterization of Super Strongly Perfect graphs in chordal and strongly chordal graphs. We have presented the results of Chordal graphs in terms of domination and co - domination numbers γ and . We have given the relationship between diameter, domination and co - domination numbers of chordal graphs. Also w

APA, Harvard, Vancouver, ISO, and other styles

2

Simonet, Geneviève, and Anne Berry. "Properties and Recognition of Atom Graphs." Algorithms 15, no. 8 (2022): 294. http://dx.doi.org/10.3390/a15080294.

Full text

Abstract:

The atom graph of a connected graph is a graph whose vertices are the atoms obtained by clique minimal separator decomposition of this graph, and whose edges are the edges of all its atom trees. A graph G is an atom graph if there is a graph whose atom graph is isomorphic to G. We study the class of atom graphs, which is also the class of atom graphs of chordal graphs, and the associated recognition problem. We prove that each atom graph is a perfect graph and give a characterization of atom graphs in terms of a spanning tree, inspired by the characterization of clique graphs of chordal graphs

APA, Harvard, Vancouver, ISO, and other styles

3

Şeker, Oylum, Pinar Heggernes, Tinaz Ekim, and Z. Caner Taşkın. "Generation of random chordal graphs using subtrees of a tree." RAIRO - Operations Research 56, no. 2 (2022): 565–82. http://dx.doi.org/10.1051/ro/2022027.

Full text

Abstract:

Chordal graphs form one of the most studied graph classes. Several graph problems that are NP-hard in general become solvable in polynomial time on chordal graphs, whereas many others remain NP-hard. For a large group of problems among the latter, approximation algorithms, parameterized algorithms, and algorithms with moderately exponential or sub-exponential running time have been designed. Chordal graphs have also gained increasing interest during the recent years in the area of enumeration algorithms. Being able to test these algorithms on instances of chordal graphs is crucial for understa

APA, Harvard, Vancouver, ISO, and other styles

4

D., Parks Allen. "Observations Concerning Chordal Graph Polynomials." International Journal of Sciences Volume 4, no. 2015-01 (2015): 36–39. https://doi.org/10.5281/zenodo.3348831.

Full text

Abstract:

For every graph that is clique equivalent to a connected chordal graph, it is shown that the associated dependence polynomial has a unit root and that the associated clique and independence polynomials have negative unit roots. The dependence polynomial for a graph that is the join of two graphs is also shown to have a unit root when at least one of the two joined graphs is clique equivalent to a connected chordal graph. A condition satisfied by the eigenvalues of graphs that are clique equivalent to connected chordal graphs with clique numbers less than four is identified.Read Complete Articl

APA, Harvard, Vancouver, ISO, and other styles

5

Reyes, M. A., C. Dalfó, and M. A. Fiol. "Structural and Spectral Properties of Chordal Ring, Multi-Ring, and Mixed Graphs." Symmetry 16, no. 9 (2024): 1135. http://dx.doi.org/10.3390/sym16091135.

Full text

Abstract:

The chordal ring (CR) graphs are a well-known family of graphs used to model some interconnection networks for computer systems in which all nodes are in a cycle. Generalizing the CR graphs, in this paper, we introduce the families of chordal multi-ring (CMR), chordal ring mixed (CRM), and chordal multi-ring mixed (CMRM) graphs. In the case of mixed graphs, we can have edges (without direction) and arcs (with direction). The chordal ring and chordal ring mixed graphs are bipartite and 3-regular. They consist of a number r (for r≥1) of (undirected or directed) cycles with some edges (the chords

APA, Harvard, Vancouver, ISO, and other styles

6

Nguyen, Ngoc Tuy, Jörg Bornemann, and Van Bang Le. "Graph classes related to chordal graphs and chordal bipartite graphs." Electronic Notes in Discrete Mathematics 27 (October 2006): 73–74. http://dx.doi.org/10.1016/j.endm.2006.08.062.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Sun, Wenbo, and Ivona Bezáková. "Sampling Random Chordal Graphs by MCMC (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 10 (2020): 13929–30. http://dx.doi.org/10.1609/aaai.v34i10.7237.

Full text

Abstract:

Chordal graphs are a widely studied graph class, with applications in several areas of computer science, including structural learning of Bayesian networks. Many problems that are hard on general graphs become solvable on chordal graphs. The random generation of instances of chordal graphs for testing these algorithms is often required. Nevertheless, there are only few known algorithms that generate random chordal graphs, and, as far as we know, none of them generate chordal graphs uniformly at random (where each chordal graph appears with equal probability). In this paper we propose a Markov

APA, Harvard, Vancouver, ISO, and other styles

8

McKee, Terry A. "Characterizing s-strongly chordal bipartite graphs." Utilitas Mathematica 123 (June 26, 2025): 99–106. https://doi.org/10.61091/um123-07.

Full text

Abstract:

<p>The strongly chordal graph literature has recently expanded to include the sequentially smaller classes of <span class="math inline">\(s\)</span>-strongly chordal graphs for <span class="math inline">\(s = 1, 2, 3,\ldots\)</span> (and the limiting class of majorly chordal graphs). These stronger classes preserve — while simultaneously intensifying — the conventional chords-of-cycles inspiration of chordal graph theory. This leads to characterizing corresponding <span class="math inline">\(s\)</span>-strongly chordal bipartite graphs and majorly chor

APA, Harvard, Vancouver, ISO, and other styles

9

Bender, E. A., L. B. Richmond, and N. C. Wormald. "Almost all chordal graphs split." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 38, no. 2 (1985): 214–21. http://dx.doi.org/10.1017/s1446788700023077.

Full text

Abstract:

AbstractA chordal graph is a graph in which every cycle of length at least 4 has a chord. If G is a random n-vertex labelled chordal graph, the size of the larget clique in about n/2 and deletion of this clique almost surely leaves only isolated vertices. This gives the asymptotic number of chordal graphs and information about a variety of things such as the size of the largest clique and connectivity.

APA, Harvard, Vancouver, ISO, and other styles

10

McKee, Terry A. "Symmetric graph-theoretic roles of two-pairs and chords of cycles." Discrete Mathematics, Algorithms and Applications 06, no. 03 (2014): 1450031. http://dx.doi.org/10.1142/s1793830914500311.

Full text

Abstract:

Although the notion of a two-pair (a pair of vertices between which all induced paths have length 2) was invented for the class of weakly chordal graphs, two-pairs can also play a fundamental role for smaller graph classes. Indeed, two-pairs and chords of cycles can collaborate symmetrically to give parallel characterizations of weakly chordal, chordal, and strongly chordal graphs (and of distance-hereditary graphs).

APA, Harvard, Vancouver, ISO, and other styles

11

Uehara, Ryuhei, Seinosuke Toda, and Takayuki Nagoya. "Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs." Discrete Applied Mathematics 145, no. 3 (2005): 479–82. http://dx.doi.org/10.1016/j.dam.2004.06.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Bermudo, Sergio, Walter Carballosa, José Rodríguez, and José Sigarreta. "On the hyperbolicity of edge-chordal and path-chordal graphs." Filomat 30, no. 9 (2016): 2599–607. http://dx.doi.org/10.2298/fil1609599b.

Full text

Abstract:

If X is a geodesic metric space and x1, x2, x3 ( X, a geodesic triangle T = {x1, x2, x3} is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is ?-hyperbolic (in the Gromov sense) if any side of T is contained in a ?-neighborhood of the union of the other two sides, for every geodesic triangle T in X. An important problem in the study of hyperbolic graphs is to relate the hyperbolicity with some classical properties in graph theory. In this paper we find a very close connection between hyperbolicity and chordality: we extend the classical definition of chordality in

APA, Harvard, Vancouver, ISO, and other styles

13

Nisse, Nicolas. "Connected graph searching in chordal graphs." Discrete Applied Mathematics 157, no. 12 (2009): 2603–10. http://dx.doi.org/10.1016/j.dam.2008.08.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Nikolopoulos, Stavros D., and Leonidas Palios. "Parallel Algorithms for Recognizing P5-free and ${\bar P}_5$-free Weakly Chordal Graphs." Parallel Processing Letters 14, no. 01 (2004): 119–29. http://dx.doi.org/10.1142/s0129626404001763.

Full text

Abstract:

We prove algorithmic characterizations of weakly chordal graphs, which lead to efficient parallel algorithms for recognizing P5-free and [Formula: see text]-free weakly chordal graphs. For an input graph on n vertices and m edges, our algorithms run in O( log 2n) time and require O(m2/ log n) processors on the EREW PRAM model of computation. The proposed recognition algorithms efficiently detect P5 s and [Formula: see text] in weakly chordal graphs in O( log n) time with O(m2/ log n) processors on the EREW PRAM. Additionally, we show how the algorithms can be augmented to provide a certificate

APA, Harvard, Vancouver, ISO, and other styles

15

McKee, Terry A. "Strengthening strongly chordal graphs." Discrete Mathematics, Algorithms and Applications 08, no. 01 (2016): 1650002. http://dx.doi.org/10.1142/s1793830916500026.

Full text

Abstract:

An [Formula: see text]-chord of a cycle [Formula: see text] is a chord that forms a new cycle with a length-[Formula: see text] subpath of [Formula: see text] when [Formula: see text] is at most half the length of [Formula: see text]. Define a graph to be [Formula: see text]-strongly chordal if, for every [Formula: see text], every cycle long enough to have an [Formula: see text]-chord always has an [Formula: see text]-chord. The [Formula: see text]-strongly chordal and [Formula: see text]-strongly chordal graphs are, respectively, the chordal and strongly chordal graphs. Several characterizat

APA, Harvard, Vancouver, ISO, and other styles

16

Lee, Chuan-Min. "Exploring Dominating Functions and Their Complexity in Subclasses of Weighted Chordal Graphs and Bipartite Graphs." Mathematics 13, no. 3 (2025): 403. https://doi.org/10.3390/math13030403.

Full text

Abstract:

Domination problems are fundamental problems in graph theory with diverse applications in optimization, network design, and computational complexity. This paper investigates {k}-domination, k-tuple domination, and their total domination variants in weighted strongly chordal graphs and chordal bipartite graphs. Specifically, the {k}-domination problem in weighted strongly chordal graphs and the total {k}-domination problem in weighted chordal bipartite graphs are shown to be solvable in O(n+m) time. For weighted proper interval graphs and convex bipartite graphs, we solve the k-tuple domination

APA, Harvard, Vancouver, ISO, and other styles

17

Emtander, Eric. "A class of hypergraphs that generalizes chordal graphs." MATHEMATICA SCANDINAVICA 106, no. 1 (2010): 50. http://dx.doi.org/10.7146/math.scand.a-15124.

Full text

Abstract:

In this paper we introduce a class of hypergraphs that we call chordal. We also extend the definition of triangulated hypergraphs, given by H. T. Hà and A. Van Tuyl, so that a triangulated hypergraph, according to our definition, is a natural generalization of a chordal (rigid circuit) graph. R. Fröberg has showed that the chordal graphs corresponds to graph algebras, $R/I(\mathcal{G})$, with linear resolutions. We extend Fröberg's method and show that the hypergraph algebras of generalized chordal hypergraphs, a class of hypergraphs that includes the chordal hypergraphs, have linear resolutio

APA, Harvard, Vancouver, ISO, and other styles

18

Agnarsson, Geir. "On chordal graphs and their chromatic polynomials." MATHEMATICA SCANDINAVICA 93, no. 2 (2003): 240. http://dx.doi.org/10.7146/math.scand.a-14421.

Full text

Abstract:

We derive a formula for the chromatic polynomial of a chordal or a triangulated graph in terms of its maximal cliques. As a corollary we obtain a way to write down an explicit formula for the chromatic polynomial for an arbitrary power of a graph which belongs to any given class of chordal graphs that are closed under taking powers.

APA, Harvard, Vancouver, ISO, and other styles

19

PRADHAN, D. "COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS." Discrete Mathematics, Algorithms and Applications 04, no. 03 (2012): 1250045. http://dx.doi.org/10.1142/s1793830912500450.

Full text

Abstract:

In this paper, we consider minimum total domination problem along with two of its variations namely, minimum signed total domination problem and minimum minus total domination problem for chordal bipartite graphs. In the minimum total domination problem, the objective is to find a smallest size subset TD ⊆ V of a given graph G = (V, E) such that |TD∩NG(v)| ≥ 1 for every v ∈ V. In the minimum signed (minus) total domination problem for a graph G = (V, E), it is required to find a function f : V → {-1, 1} ({-1, 0, 1}) such that f(NG(v)) = ∑u∈NG(v)f(u) ≥ 1 for each v ∈ V, and the cost f(V) = ∑v∈V

APA, Harvard, Vancouver, ISO, and other styles

20

TALMACIU, MIHAI. "On Hyper-Chordal graphs." Carpathian Journal of Mathematics 37, no. 1 (2021): 119–26. http://dx.doi.org/10.37193/cjm.2021.01.12.

Full text

Abstract:

Triangulated graphs have many interesting properties (perfection, recognition algorithms, combinatorial optimization algorithms with linear complexity). Hyper-triangulated graphs are those where each induced subgraph has a hyper-simplicial vertex. In this paper we give the characterizations of hyper-triangulated graphs using an ordering of vertices and the weak decomposition. We also offer a recognition algorithm for the hyper-triangulated graphs, the inclusions between the triangulated graphs generalizations and we show that any hyper-triangulated graph is perfect.

APA, Harvard, Vancouver, ISO, and other styles

21

Ma, Xuanlong. "Forbidden Subgraphs in Intersection Power Graphs of Finite Groups." Algebra Colloquium 32, no. 01 (2025): 95–110. https://doi.org/10.1142/s1005386725000094.

Full text

Abstract:

The intersection power graph of a finite group [Formula: see text] is a simple graph whose vertex set is [Formula: see text], in which two distinct vertices [Formula: see text] and [Formula: see text] are adjacent if and only if either one of [Formula: see text] and [Formula: see text] is the identity element, or [Formula: see text] is non-trivial. A number of important graph classes, including cographs, chordal graphs, split graphs, and threshold graphs, can be defined either structurally or in terms of forbidden induced subgraphs. In this paper, we characterize the finite groups whose inters

APA, Harvard, Vancouver, ISO, and other styles

22

Guo, Jin, Yi-Huang Shen, and Tongsuo Wu. "Edgewise strongly shellable clutters." Journal of Algebra and Its Applications 17, no. 01 (2018): 1850018. http://dx.doi.org/10.1142/s0219498818500184.

Full text

Abstract:

When [Formula: see text] is a chordal clutter in the sense of Woodroofe or Emtander, we show that the complement clutter is edgewise strongly shellable. When [Formula: see text] is indeed a finite simple graph, we provide additional characterization of chordal graphs from the point of view of strong shellability. In particular, the generic graph [Formula: see text] of a tree is shown to be bi-strongly shellable.

APA, Harvard, Vancouver, ISO, and other styles

23

Takaoka, Asahi. "Complexity of Hamiltonian Cycle Reconfiguration." Algorithms 11, no. 9 (2018): 140. http://dx.doi.org/10.3390/a11090140.

Full text

Abstract:

The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles C 0 and C t of a graph G, whether there is a sequence of Hamiltonian cycles C 0 , C 1 , … , C t such that C i can be obtained from C i − 1 by a switch for each i with 1 ≤ i ≤ t , where a switch is the replacement of a pair of edges u v and w z on a Hamiltonian cycle with the edges u w and v z of G, given that u w and v z did not appear on the cycle. We show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete, settling an open question posed by Ito et al. (2011) and van den Heuvel (2013). More pre

APA, Harvard, Vancouver, ISO, and other styles

24

Nagarathinam, R., N. Parvathi, and . "Grundy Number of Some Chordal Graphs." International Journal of Engineering & Technology 7, no. 4.10 (2018): 64. http://dx.doi.org/10.14419/ijet.v7i4.10.20708.

Full text

Abstract:

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c : V → {1, 2, . . .} such that c(u) 12â‰ "> c(v) for every edge uv ∈ E. For proper coloring, colors assigned must be minimum, but for Grundy coloring which should be maximum. In this instance, Grundy numbers of chordal graphs like Cartesian product of two path graphs, join of the path and complete graphs and the line graph of tadpole have been executed

APA, Harvard, Vancouver, ISO, and other styles

25

Panda, B. S., and D. Pradhan. "A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs." Discrete Mathematics, Algorithms and Applications 07, no. 02 (2015): 1550020. http://dx.doi.org/10.1142/s1793830915500202.

Full text

Abstract:

A set D ⊆ V is a restrained dominating set of a graph G = (V, E) if every vertex in V\D is adjacent to a vertex in D and a vertex in V\D. Given a graph G and a positive integer k, the restrained domination problem is to check whether G has a restrained dominating set of size at most k. The restrained domination problem is known to be NP-complete even for chordal graphs. In this paper, we propose a linear time algorithm to compute a minimum restrained dominating set of a proper interval graph. We present a polynomial time reduction that proves the NP-completeness of the restrained domination pr

APA, Harvard, Vancouver, ISO, and other styles

26

Sun, Wenbo. "Sampling and Counting Acyclic Orientations in Chordal Graphs (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 11 (2022): 13061–62. http://dx.doi.org/10.1609/aaai.v36i11.21667.

Full text

Abstract:

Sampling of chordal graphs and various types of acyclic orientations over chordal graphs plays a central role in several AI applications such as causal structure learning. For a given undirected graph, an acyclic orientation is an assignment of directions to all of its edges which makes the resulting directed graph cycle-free. Sampling is often closely related to the corresponding counting problem. Counting of acyclic orientations of a given chordal graph can be done in polynomial time, but the previously known techniques do not seem to lead to a corresponding (efficient) sampler. In this work

APA, Harvard, Vancouver, ISO, and other styles

27

Fomin, Fedor V., and Petr A. Golovach. "Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs." Algorithmica 83, no. 7 (2021): 2170–214. http://dx.doi.org/10.1007/s00453-021-00822-x.

Full text

Abstract:

AbstractWe study algorithmic properties of the graph class $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e , that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e . More precisely, we identify a large class of optimization problems on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e solvable in time $$2^{{\mathcal{

APA, Harvard, Vancouver, ISO, and other styles

28

Ibarra, Louis. "The clique-separator graph for chordal graphs." Discrete Applied Mathematics 157, no. 8 (2009): 1737–49. http://dx.doi.org/10.1016/j.dam.2009.02.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

PANDA, B. S., VIJAY NATARAJAN, and SAJAL K. DAS. "PARALLEL ALGORITHMS FOR HAMILTONIAN 2-SEPARATOR CHORDAL GRAPHS." Parallel Processing Letters 12, no. 01 (2002): 51–64. http://dx.doi.org/10.1142/s0129626402000823.

Full text

Abstract:

In this paper we propose a parallel algorithm to construct a one-sided monotone polygon from a Hamiltonian 2-separator chordal graph. The algorithm requires O( log n) time and O(n) processors on the CREW PRAM model, where n is the number of vertices and m is the number of edges in the graph. We also propose parallel algorithms to recognize Hamiltonian 2-separator chordal graphs and to construct a Hamiltonian cycle in such a graph. They run in O( log 2 n) time using O(mn) processors on the CRCW PRAM model and O( log 2 n) time using O(m) processors on the CREW PRAM model, respectively.

APA, Harvard, Vancouver, ISO, and other styles

30

DOHMEN, KLAUS. "Bonferroni-Type Inequalities via Chordal Graphs." Combinatorics, Probability and Computing 11, no. 4 (2002): 349–51. http://dx.doi.org/10.1017/s0963548302005151.

Full text

Abstract:

Let {Av}v∈V be a finite collection of events and G = (V, E) be a chordal graph. Our main result – the chordal graph sieve – is a Bonferroni-type inequality where the selection of intersections in the estimates is determined by a chordal graph G. It interpolates between Boole's inequality (G empty) and the sieve formula (G complete). By varying G, several inequalities both well-known and new are obtained in a concise and unified way.

APA, Harvard, Vancouver, ISO, and other styles

31

Jose, Bibin K. "Some New Classes of Open Distance-Pattern Uniform Graphs." International Journal of Combinatorics 2013 (July 24, 2013): 1–7. http://dx.doi.org/10.1155/2013/863439.

Full text

Abstract:

Given an arbitrary nonempty subset M of vertices in a graph G=(V,E), each vertex u in G is associated with the set fMo(u)={d(u,v):v∈M,u≠v} and called its open M-distance-pattern. The graph G is called open distance-pattern uniform (odpu-) graph if there exists a subset M of V(G) such that fMo(u)=fMo(v) for all u,v∈V(G), and M is called an open distance-pattern uniform (odpu-) set of G. The minimum cardinality of an odpu-set in G, if it exists, is called the odpu-number of G and is denoted by od(G). Given some property P, we establish characterization of odpu-graph with property P. In this pape

APA, Harvard, Vancouver, ISO, and other styles

32

Ali, Shahzad, Shahzaib Ashraf, Shahbaz Ali, Abdullah Afzal, and Amal S. Alali. "On Local Fractional Topological Indices and Entropies for Hyper-Chordal Ring Networks Using Local Fractional Metric Dimension." Symmetry 17, no. 1 (2024): 5. https://doi.org/10.3390/sym17010005.

Full text

Abstract:

An algebraic graph is defined in terms of graph theory as a graph with related algebraic structures or characteristics. If the vertex set of a graph G is a group, a ring, or a field, then G is called an algebraic structure graph. This work uses an algebraic structure graph based on the modular ring Zn, known as a hyper-chordal ring network. The lower and upper bounds of the local fractional metric dimension are computed for certain families of hyper-chordal ring networks. Utilizing the cardinalities of local fractional resolving sets, local fractional resolving (LFR)M-polynomials are computed

APA, Harvard, Vancouver, ISO, and other styles

33

SHERMAN, DAVID, MING TSAI, CHENG-KUAN LIN, et al. "4-ORDERED HAMILTONICITY FOR SOME CHORDAL RING GRAPHS." Journal of Interconnection Networks 11, no. 03n04 (2010): 157–74. http://dx.doi.org/10.1142/s0219265910002787.

Full text

Abstract:

A graph G is k-ordered if for any sequence of k distinct vertices of G, there exists a cycle in G containing these k vertices in the specified order. It is k-ordered Hamiltonian if, in addition, the required cycle is Hamiltonian. The question of the existence of an infinite class of 3-regular 4-ordered Hamiltonian graphs was posed in 1997 by Ng and Schultz.13At the time, the only known examples were K4and K3,3. Some progress was made in 2008 by Mészáros,12when the Peterson graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered Hamiltonian; moreover, an infinite class

APA, Harvard, Vancouver, ISO, and other styles

34

Erey, Nursel, and Ayesha Asloob Qureshi. "Second Powers of Cover Ideals of Paths." Algebra Colloquium 29, no. 04 (2022): 669–86. http://dx.doi.org/10.1142/s1005386722000487.

Full text

Abstract:

We show that the second power of the cover ideal of a path graph has linear quotients. To prove our result we construct a recursively defined order on the generators of the ideal which yields linear quotients. Our construction has a natural generalization to the larger class of chordal graphs. This generalization allows us to raise some questions that are related to some open problems about powers of cover ideals of chordal graphs.

APA, Harvard, Vancouver, ISO, and other styles

35

Scheidweiler, Robert, and Sebastian Wiederrecht. "On chordal graph and line graph squares." Discrete Applied Mathematics 243 (July 2018): 239–47. http://dx.doi.org/10.1016/j.dam.2018.02.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Tang, C. Y., M. T. Ko, C. W. Ho, T. s. Hsu, and S. L. Peng. "Graph Searching on Some Subclasses of Chordal Graphs." Algorithmica 27, no. 3 (2000): 395–426. http://dx.doi.org/10.1007/s004530010026.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Argiroffo, Gabriela, Valeria Leoni, and Pablo Torres. "-domination for chordal graphs and related graph classes." Electronic Notes in Discrete Mathematics 44 (November 2013): 219–24. http://dx.doi.org/10.1016/j.endm.2013.10.034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Changat, Manoj, Lekshmi Kamal K. Sheela, and Prasanth G. Narasimha-Shenoi. "Axiomatic characterizations of Ptolemaic and chordal graphs." Opuscula Mathematica 43, no. 3 (2023): 393–407. http://dx.doi.org/10.7494/opmath.2023.43.3.393.

Full text

Abstract:

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 of a general set function termed as a transit function defined on the Cartesian product of a non-empty set \(V\) to the power set of \(V\) satisfying the expansive, symmetric and idempotent axioms. In this paper, we propose a set of independent first order betweenness axioms on an arbitrary transit function and provide characterization of the

APA, Harvard, Vancouver, ISO, and other styles

39

NARAYANASWAMY, N. S., and N. SADAGOPAN. "A UNIFIED FRAMEWORK FOR BI(TRI)CONNECTIVITY AND CHORDAL AUGMENTATION." International Journal of Foundations of Computer Science 24, no. 01 (2013): 67–93. http://dx.doi.org/10.1142/s0129054113400054.

Full text

Abstract:

For a connected non-complete graph, a vertex separator is a subset of vertices whose deletion increases the number of connected components and the vertex connectivity of the graph refers to the size of a minimum vertex separator. A graph with the vertex connectivity k is said to be k-vertex connected. Given a k-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (k + 1)-vertex connected. In this paper, we report our study on connectivity augmentation in 1-connected graphs, 2-connected graphs, and k-connected chordal gra

APA, Harvard, Vancouver, ISO, and other styles

40

Rahman, Md Zamilur, Asish Mukhopadhyay, and Yash P. Aneja. "A separator-based method for generating weakly chordal graphs." Discrete Mathematics, Algorithms and Applications 12, no. 04 (2020): 2050039. http://dx.doi.org/10.1142/s1793830920500391.

Full text

Abstract:

We propose a scheme for generating a weakly chordal graph on [Formula: see text] vertices with [Formula: see text] edges. In this method, we first construct a tree and then generate an orthogonal layout (which is a weakly chordal graph on the [Formula: see text] vertices) based on this tree. We then insert additional edges, if needed, for a total of [Formula: see text] edges. Our algorithm ensures that the graph remains weakly chordal after each edge is inserted. The time complexity of an insertion query is [Formula: see text], where [Formula: see text] and [Formula: see text] are the degrees

APA, Harvard, Vancouver, ISO, and other styles

41

Alkam, Osama, and Emad Abu Osba. "Zero Divisor Graph for the Ring of Eisenstein Integers Modulo n." Algebra 2014 (December 15, 2014): 1–6. http://dx.doi.org/10.1155/2014/146873.

Full text

Abstract:

Let En be the ring of Eisenstein integers modulo n. In this paper we study the zero divisor graph Γ(En). We find the diameters and girths for such zero divisor graphs and characterize n for which the graph Γ(En) is complete, complete bipartite, bipartite, regular, Eulerian, Hamiltonian, or chordal.

APA, Harvard, Vancouver, ISO, and other styles

42

Erdős, Paul, Edward T. Ordman, and Yechezkel Zalcstein. "Clique Partitions of Chordal Graphs." Combinatorics, Probability and Computing 2, no. 4 (1993): 409–15. http://dx.doi.org/10.1017/s0963548300000808.

Full text

Abstract:

To partition the edges of a chordal graph on n vertices into cliques may require as many as n2/6 cliques; there is an example requiring this many, which is also a threshold graph and a split graph. It is unknown whether this many cliques will always suffice. We are able to show that (1 − c)n2/4 cliques will suffice for some c > 0.

APA, Harvard, Vancouver, ISO, and other styles

43

Sun, Wenbo, and Ivona Bezáková. "Sampling Partial Acyclic Orientations in Chordal Graphs by the Lovasz Local Lemma (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 18 (2021): 15901–2. http://dx.doi.org/10.1609/aaai.v35i18.17947.

Full text

Abstract:

Sampling of various types of acyclic orientations of chordal graphs plays a central role in several AI applications. In this work we investigate the use of the recently proposed general partial rejection sampling technique of Guo, Jerrum, and Liu, based on the Lovasz Local Lemma, for sampling partial acyclic orientations. For a given undirected graph, an acyclic orientation is an assignment of directions to all of its edges so that there is no directed cycle. In partial orientations some edges are allowed to be undirected. We show how the technique can be used to sample partial acyclic orienta

APA, Harvard, Vancouver, ISO, and other styles

44

Feghali, Carl, and Jiří Fiala. "Reconfiguration graph for vertex colourings of weakly chordal graphs." Discrete Mathematics 343, no. 3 (2020): 111733. http://dx.doi.org/10.1016/j.disc.2019.111733.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Ekim, Tınaz, Mordechai Shalom, and Oylum Şeker. "The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation." Journal of Combinatorial Optimization 41, no. 3 (2021): 710–35. http://dx.doi.org/10.1007/s10878-021-00712-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

D., Parks Allen. "Clique Complex Homology: A Combinatorial Invariant for Chordal Graphs." International Journal of Sciences Volume 2, no. 2013-07 (2013): 96–100. https://doi.org/10.5281/zenodo.3348240.

Full text

Abstract:

It is shown that a geometric realization of the clique complex of a connected chordal graph is homologically trivial and as a consequence of this it is always the case for any connected chordal graph G that ∑_(k=1)^ω(G)▒(-1)^(k-1) η_k (G)=1, where η_k (G) is the number of cliques of order k in G and ω(G) is the clique number of G.Read Complete Article at ijSciences: V2201306194

APA, Harvard, Vancouver, ISO, and other styles

47

Lee, Chuan-Min. "Weighted Maximum-Clique Transversal Sets of Graphs." ISRN Discrete Mathematics 2011 (January 26, 2011): 1–20. http://dx.doi.org/10.5402/2011/540834.

Full text

Abstract:

A maximum-clique transversal set of a graph G is a subset of vertices intersecting all maximum cliques of G. The maximum-clique transversal set problem is to find a maximum-clique transversal set of G of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, Chang, Kloks, and Lee introduced the concept of maximum-clique transversal sets on graphs in 2001. In this paper, we study the weighted version of the maximum-clique transversal set problem for split graphs, balanced graphs, strongly chordal graph, Helly circular-arc graphs, comparability graphs, distance-

APA, Harvard, Vancouver, ISO, and other styles

48

Lin, In-Jen, Terry A. McKee, and D. B. West. "The leafage of a chordal graph." Discussiones Mathematicae Graph Theory 18, no. 1 (1998): 23. http://dx.doi.org/10.7151/dmgt.1061.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Khamis, H. J., and T. A. McKee. "Chordal Graph Models of Contingency Tables." Computers & Mathematics with Applications 34, no. 11 (1997): 89–97. http://dx.doi.org/10.1016/s0898-1221(97)00222-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Harary, Frank, and Terry A. McKee. "The square of a chordal graph." Discrete Mathematics 128, no. 1-3 (1994): 165–72. http://dx.doi.org/10.1016/0012-365x(94)90110-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!