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 11 Next

Displaying 201 – 220 of 376

Showing per page

Nonempty intersection of longest paths in a graph with a small matching number

Fuyuan Chen (2015)

Czechoslovak Mathematical Journal

A maximum matching of a graph G is a matching of G with the largest number of edges. The matching number of a graph G , denoted by α ' ( G ) , is the number of edges in a maximum matching of G . In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Although this conjecture has been disproved, finding some nice classes of graphs that support this conjecture is still very meaningful and interesting. In this short note, we prove that Gallai’s conjecture is true for...

Non-hyperbolicity in random regular graphs and their traffic characteristics

Gabriel Tucci (2013)

Open Mathematics

In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n logd−13 n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.

Note on independent sets of a graph

Jaroslav Ivančo (1994)

Mathematica Bohemica

Let the number of k -element sets of independent vertices and edges of a graph G be denoted by n ( G , k ) and m ( G , k ) , respectively. It is shown that the graphs whose every component is a circuit are the only graphs for which the equality n ( G , k ) = m ( G , k ) is satisfied for all values of k .

On 2-periodic graphs of a certain graph operator

Ivan Havel, Bohdan Zelinka (2001)

Discussiones Mathematicae Graph Theory

We deal with the graph operator P o w ₂ ¯ defined to be the complement of the square of a graph: P o w ₂ ¯ ( G ) = P o w ₂ ( G ) ¯ . Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph K m , n can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective geometries...

On 3-simplicial vertices in planar graphs

Endre Boros, Robert E. Jamison, Renu Laskar, Henry Martyn Mulder (2004)

Discussiones Mathematicae Graph Theory

A vertex v in a graph G = (V,E) is k-simplicial if the neighborhood N(v) of v can be vertex-covered by k or fewer complete graphs. The main result of the paper states that a planar graph of order at least four has at least four 3-simplicial vertices of degree at most five. This result is a strengthening of the classical corollary of Euler's Formula that a planar graph of order at least four contains at least four vertices of degree at most five.

On a generalization of the friendship theorem

Mohammad Hailat (2012)

Discussiones Mathematicae Graph Theory

The Friendship Theorem states that if any two people, of a group of at least three people, have exactly one friend in common, then there is always a person who is everybody's friend. In this paper, we generalize the Friendship Theorem to the case that in a group of at least three people, if every two friends have one or two common friends and every pair of strangers have exactly one friend then there exist one person who is friend to everybody in the group. In particular, we show that the graph...

Currently displaying 201 – 220 of 376