All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 5 Next

Displaying 81 – 100 of 908

Showing per page

On a problem of E. Prisner concerning the biclique operator

Bohdan Zelinka (2002)

Mathematica Bohemica

The symbol K ( B , C ) denotes a directed graph with the vertex set B ∪ C for two (not necessarily disjoint) vertex sets B , C in which an arc goes from each vertex of B into each vertex of C . A subdigraph of a digraph D which has this form is called a bisimplex in D . A biclique in D is a bisimplex in D which is not a proper subgraph of any other and in which B ≠ ∅ and C ≠ ∅ . The biclique digraph C → ( D ) of D is the digraph whose vertex set is the set of all bicliques in D and in which there is an arc from K ( B 1 , C 1 ) into K ( B 2 , C 2 ) if and only...

On a problem of walks

Charles Delorme, Marie-Claude Heydemann (1999)

Annales de l'institut Fourier

In 1995, F. Jaeger and M.-C. Heydemann began to work on a conjecture on binary operations which are related to homomorphisms of De Bruijn digraphs. For this, they have considered the class of digraphs G such that for any integer k , G has exactly n walks of length k , where n is the order of G . Recently, C. Delorme has obtained some results on the original conjecture. The aim of this paper is to recall the conjecture and to report where all the authors arrived.

On a property of neighborhood hypergraphs

Konrad Pióro (2006)

Commentationes Mathematicae Universitatis Carolinae

The aim of the paper is to show that no simple graph has a proper subgraph with the same neighborhood hypergraph. As a simple consequence of this result we infer that if a clique hypergraph 𝒢 and a hypergraph ℋ have the same neighborhood hypergraph and the neighborhood relation in 𝒢 is a subrelation of such a relation in ℋ , then ℋ is inscribed into 𝒢 (both seen as coverings). In particular, if ℋ is also a clique hypergraph, then ℋ = 𝒢 .

On a Spanning k-Tree in which Specified Vertices Have Degree Less Than k

Hajime Matsumura (2015)

Discussiones Mathematicae Graph Theory

A k-tree is a tree with maximum degree at most k. In this paper, we give a degree sum condition for a graph to have a spanning k-tree in which specified vertices have degree less than k. We denote by σk(G) the minimum value of the degree sum of k independent vertices in a graph G. Let k ≥ 3 and s ≥ 0 be integers, and suppose G is a connected graph and σk(G) ≥ |V (G)|+s−1. Then for any s specified vertices, G contains a spanning k-tree in which every specified vertex has degree less than k. The degree...

On a special case of Hadwiger's conjecture

Michael D. Plummer, Michael Stiebitz, Bjarne Toft (2003)

Discussiones Mathematicae Graph Theory

Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.

On a sphere of influence graph in a one-dimensional space

Zbigniew Palka, Monika Sperling (2005)

Discussiones Mathematicae Graph Theory

A sphere of influence graph generated by a finite population of generated points on the real line by a Poisson process is considered. We determine the expected number and variance of societies formed by population of n points in a one-dimensional space.

On acyclic colorings of direct products

Simon Špacapan, Aleksandra Tepeh Horvat (2008)

Discussiones Mathematicae Graph Theory

A coloring of a graph G is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees T₁ and T₂ equals min{Δ(T₁) + 1, Δ(T₂) + 1}. We also prove that the acyclic chromatic number of direct product of two complete graphs Kₘ and Kₙ is mn-m-2, where m ≥ n ≥ 4. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.

Currently displaying 81 – 100 of 908