EuDML | Browse

Displaying 61 – 71 of 71

On the simplex graph operator

Bohdan Zelinka (1998)

Discussiones Mathematicae Graph Theory

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.

On the tree-width of a graph.

Chlebíková, J. (1992)

Acta Mathematica Universitatis Comenianae. New Series

On transitive orientations of G-ê

Michael Andresen (2009)

Discussiones Mathematicae Graph Theory

A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge ê∈ E we explore the question whether the graph G-ê, obtained by removing the undirected edge ê, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.

On two graph-theoretical problems from the conference at Nová Ves u Branžeže

Bohdan Zelinka (1981)

Časopis pro pěstování matematiky

On two transformations of graphs

Bohdan Zelinka (1997)

Mathematica Bohemica

The paper describes the properties of two transformations of graphs. One of them was introduced by F. Gliviak for the sake of study of metric properties of graphs, the other is related to it.

On uniquely partitionable relational structures and object systems

Jozef Bucko, Peter Mihók (2006)

Discussiones Mathematicae Graph Theory

We introduce object systems as a common generalization of graphs, hypergraphs, digraphs and relational structures. Let C be a concrete category, a simple object system over C is an ordered pair S = (V,E), where E = A₁,A₂,...,Aₘ is a finite set of the objects of C, such that the ground-set $V (A_{i})$ of each object $A_{i} \in E$ is a finite set with at least two elements and $V \supseteq ⋃_{i = 1}^{m} V (A_{i})$ . To generalize the results on graph colourings to simple object systems we define, analogously as for graphs, that an additive induced-hereditary...

On universal cycles of labeled graphs.

Brockman, Greg, Kay, Bill, Snively, Emma E. (2010)

The Electronic Journal of Combinatorics [electronic only]

On Γ-regular graphs

J. Płonka (1982)

Colloquium Mathematicae

On θ-graphs of partial cubes

Sandi Klavžar, Matjaz Kovse (2007)

Discussiones Mathematicae Graph Theory

The Θ-graph Θ(G) of a partial cube G is the intersection graph of the equivalence classes of the Djoković-Winkler relation. Θ-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, Θ(G) is complete if and only if G can be obtained from K₁ by a sequence of (newly introduced) dense expansions. Θ-graphs are also compared with familiar concepts of crossing graphs and τ-graphs.

Operations on well-covered graphs and the Roller-Coaster conjecture.

Matchett, Philip (2004)

The Electronic Journal of Combinatorics [electronic only]

Order of the smallest counterexample to Gallai's conjecture

Fuyuan Chen (2018)

Czechoslovak Mathematical Journal

In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Zamfirescu conjectured that the smallest counterexample to Gallai’s conjecture is a graph on 12 vertices. We prove that Gallai’s conjecture is true for every connected graph $G$ with $α^{'} (G) \leq 5$ , which implies that Zamfirescu’s conjecture is true.

Displaying 61 – 71 of 71

Currently displaying 61 – 71 of 71