Displaying similar documents to “Some news about oblique graphs”

Characterization Of Super-Radial Graphs

K.M. Kathiresan, G. Marimuthu, C. Parameswaran (2014)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, the distance d(u, v) between a pair of vertices u and v is the length of a shortest path joining them. The eccentricity e(u) of a vertex u is the distance to a vertex farthest from u. The minimum eccentricity is called the radius, r(G), of the graph and the maximum eccentricity is called the diameter, d(G), of the graph. The super-radial graph R*(G) based on G has the vertex set as in G and two vertices u and v are adjacent in R*(G) if the distance between them in G is...

The edge C₄ graph of some graph classes

Manju K. Menon, A. Vijayakumar (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(G). It is shown that for any graph G without isolated vertices,...

Recognizing Chordal Graphs: Lex BFS and MCS 1

Broderick Arneson, Piotr Rudnicki (2006)

Formalized Mathematics

Similarity:

We are formalizing the algorithm for recognizing chordal graphs by lexicographic breadth-first search as presented in [13, Section 3 of Chapter 4, pp. 81-84]. Then we follow with a formalization of another algorithm serving the same end but based on maximum cardinality search as presented by Tarjan and Yannakakis [25].This work is a part of the MSc work of the first author under supervision of the second author. We would like to thank one of the anonymous reviewers for very useful suggestions. ...

Regularity and Planarity of Token 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.

On the simplex graph operator

Bohdan Zelinka (1998)

Discussiones Mathematicae Graph Theory

Similarity:

A simplex of a graph G is a subgraph of G which is a complete graph. The simplex graph Simp(G) of G is the graph whose vertex set is the set of all simplices of G and in which two vertices are adjacent if and only if they have a non-empty intersection. The simplex graph operator is the operator which to every graph G assigns its simplex graph Simp(G). The paper studies graphs which are fixed in this operator and gives a partial answer to a problem suggested by E. Prisner.