In this paper, we study the maximal prime subgraphs and their corresponding structure for any undirected graph. We introduce the notion of junction trees and investigate their structural characteristics, including junction properties, induced-subtree properties, running-intersection properties and maximum-weight spanning tree properties. Furthermore, the characters of leaves and edges on junction trees are discussed.
WANG Xiaofei, GUO Jianhua
. Junction trees of general graphs[J]. Frontiers of Mathematics in China, 2008
, 3(3)
: 399
-413
.
DOI: 10.1007/s11464-008-0023-z
1. Berry A, Bordat J P . Separability generalizesDirac's theorem. Discrete Applied Mathematics, 1998, 84: 43–53. doi:10.1016/S0166‐218X(98)00005‐5
2. Blair J R S, Peyton B W . An introduction to chordalgraphs and clique trees. In: George J A, Liu J W H, Eds. Sparse Matrix Computations: Graph Theory Issues and Algorithms, IMAVolumes in Mathematics and Its Applications, Vol 56. Berlin: Springer-Verlag, 1993, 1–30
3. Buneman P . Acharacterization of rigid circuit graphs. Discrete Math, 1974, 9: 205–212. doi:10.1016/0012‐365X(74)90002‐8
4. Darroch J N, Lauritzen S L, Speed T P . Markov fields and log-linear interaction models for contingencytables. Ann Statist, 1980, 8: 522–539. doi:10.1214/aos/1176345006
5. Diestel R . GraphDecomposition-A Study in Infinite Graph Theory. Oxford: Clarendon Press, 1990
6. Dirac G A . On rigid circuit graphs. Abh Math SemUniv Hamburg, 1961, 25: 71–76
7. Gavril F . Theintersection graphs of subtrees in trees are exactly the chordal graphs. J Combin Theory, Ser B, 1974, 16: 47–56. doi:10.1016/0095‐8956(74)90094‐X
8. Leimer H G . Optimal decomposition by clique separators. Discrete Math, 1993, 113: 99–123. doi:10.1016/0012‐365X(93)90510‐Z
9. Lekkerkerker C G, Boland J C . Representation of a finitegraph by a set of intervals on the real line. Fund Math Polska Akad Nauk, 1962, 51: 45–64
10. Tarjan R E . Decomposition by clique separators. DiscreteMath, 1985, 55: 221–232. doi:10.1016/0012‐365X(85)90051‐2
11. Walter J . Representationsof rigid cycle graphs. Dissertation forthe Doctoral Degree. Detroit: Wayne State University, 1972
12. Xu P F, Guo J H . Optimal triangulation ofBayesian networks by decomposition. TechnicalReport KLAS#07-003. Changchun: Northeast Normal University, 2007
