André Bouchet (1999)
Annales de l'institut Fourier
Similarity:
The following result is proved: if a bipartite graph is not a circle graph, then its complement is not a circle graph. The proof uses Naji’s characterization of circle graphs by means of a linear system of equations with unknowns in . At the end of this short note I briefly recall the work of François Jaeger on circle graphs.
Andrey A. Dobrynin, Leonid S. Mel'nikov (2012)
Discussiones Mathematicae Graph Theory
Similarity:
Let G be a simple 4-regular plane graph and let S be a decomposition of G into edge-disjoint cycles. Suppose that every two adjacent edges on a face belong to different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Studies of coloring of graphs of this kind were originated by Grötzsch. Two 4-chromatic graphs generated by circles in the plane were constructed by Koester in 1984 [10,11,12]. Until now, no other examples...
Mihály Bakonyi, Aaron Bono (1997)
Czechoslovak Mathematical Journal
Similarity:
The question of generalizing results involving chordal graphs to similar concepts for chordal bipartite graphs is addressed. First, it is found that the removal of a bisimplicial edge from a chordal bipartite graph produces a chordal bipartite graph. As consequence, occurance of arithmetic zeros will not terminate perfect Gaussian elimination on sparse matrices having associated a chordal bipartite graph. Next, a property concerning minimal edge separators is presented. Finally, it is...
Simić, Slobodan K. (1988)
Publications de l'Institut Mathématique. Nouvelle Série
Similarity:
Gurusamy Rengasamy Vijayakumar (2013)
Discussiones Mathematicae Graph Theory
Similarity:
The infimum of the least eigenvalues of all finite induced subgraphs of an infinite graph is defined to be its least eigenvalue. In [P.J. Cameron, J.M. Goethals, J.J. Seidel and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976) 305-327], the class of all finite graphs whose least eigenvalues ≥ −2 has been classified: (1) If a (finite) graph is connected and its least eigenvalue is at least −2, then either it is a generalized line graph or it is represented...
Terry A. McKee (2011)
Discussiones Mathematicae Graph Theory
Similarity:
Define a complete subgraph Q to be simplicial in a graph G when Q is contained in exactly one maximal complete subgraph ('maxclique') of G; otherwise, Q is nonsimplicial. Several graph classes-including strong p-Helly graphs and strongly chordal graphs-are shown to have pairs of peculiarly related new characterizations: (i) for every k ≤ 2, a certain property holds for the complete subgraphs that are in k or more maxcliques of G, and (ii) in every induced subgraph H of G, that...
Aneta Dudek, A. Paweł Wojda (2004)
Discussiones Mathematicae Graph Theory
Similarity:
A graph G is said to be H-saturated if G is H-free i.e., (G has no subgraph isomorphic to H) and adding any new edge to G creates a copy of H in G. In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size sat(n;Pₘ) of Pₘ-saturated graph of order n. They gave the number sat(n;Pₘ) for n big enough. We deal with similar problem for bipartite graphs.
Walter Carballosa, Ruy Fabila-Monroy, Jesús Leaños, Luis Manuel Rivera (2017)
Discussiones Mathematicae Graph Theory
Similarity:
Let G = (V, E) be a graph of order n and let 1 ≤ k < n be an integer. The k-token graph of G is the graph whose vertices are all the k-subsets of V, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper we characterize precisely, for each value of k, which graphs have a regular k-token graph and which connected graphs have a planar k-token graph.
Sizhong Zhou, Jiancheng Wu, Tao Zhang (2017)
Discussiones Mathematicae Graph Theory
Similarity:
A spanning subgraph F of a graph G is called a P≥3-factor of G if every component of F is a path of order at least 3. A graph G is called a P≥3-factor covered graph if G has a P≥3-factor including e for any e ∈ E(G). In this paper, we obtain three sufficient conditions for graphs to be P≥3-factor covered graphs. Furthermore, it is shown that the results are sharp.
I.B. Lackovic, D.M. Cvetkovic (1976)
Publications de l'Institut Mathématique [Elektronische Ressource]
Similarity:
Boštjan Brešar, Manoj Changat, Ajitha R. Subhamathi, Aleksandra Tepeh (2010)
Discussiones Mathematicae Graph Theory
Similarity:
The periphery graph of a median graph is the intersection graph of its peripheral subgraphs. We show that every graph without a universal vertex can be realized as the periphery graph of a median graph. We characterize those median graphs whose periphery graph is the join of two graphs and show that they are precisely Cartesian products of median graphs. Path-like median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are...
Al-Addasi, Salah, Al-Ezeh, Hasan (2008)
International Journal of Mathematics and Mathematical Sciences
Similarity: