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

Displaying 301 – 320 of 5365

Showing per page

A note on solvable vertex stabilizers of s -transitive graphs of prime valency

Song-Tao Guo, Hailong Hou, Yong Xu (2015)

Czechoslovak Mathematical Journal

A graph X , with a group G of automorphisms of X , is said to be ( G , s ) -transitive, for some s ≥ 1 , if G is transitive on s -arcs but not on ( s + 1 ) -arcs. Let X be a connected ( G , s ) -transitive graph of prime valency p ≥ 5 , and G v the vertex stabilizer of a vertex v ∈ V ( X ) . Suppose that G v is solvable. Weiss (1974) proved that | G v | ∣ p ( p - 1 ) 2 . In this paper, we prove that G v ≅ ( ℤ p ⋊ ℤ m ) × ℤ n for some positive integers m and n such that n div m and m ∣ p - 1 .

A note on strong and co-strong perfectness of the X-join of graphs

Alina Szelecka, Andrzej Włoch (1996)

Discussiones Mathematicae Graph Theory

Strongly perfect graphs were introduced by C. Berge and P. Duchet in [1]. In [4], [3] the following was studied: the problem of strong perfectness for the Cartesian product, the tensor product, the symmetrical difference of n, n ≥ 2, graphs and for the generalized Cartesian product of graphs. Co-strong perfectness was first studied by G. Ravindra andD. Basavayya [5]. In this paper we discuss strong perfectness and co-strong perfectness for the generalized composition (the lexicographic product)...

A note on strongly multiplicative graphs

Chandrashekar Adiga, H.N. Ramaswamy, D.D. Somashekara (2004)

Discussiones Mathematicae Graph Theory

In this note we give an upper bound for λ(n), the maximum number of edges in a strongly multiplicative graph of order n, which is sharper than the upper bound obtained by Beineke and Hegde [1].

A note on the Chvátal-rank of clique family inequalities

Arnaud Pêcher, Annegret K. Wagler (2007)

RAIRO - Operations Research


Clique family inequalities a∑v∈W xv + (a - 1)∈v∈W, xv ≤ aδ form an intriguing class of valid inequalities for the stable set polytopes of all graphs. We prove firstly that their Chvátal-rank is at most a, which provides an alternative proof for the validity of clique family inequalities, involving only standard rounding arguments. Secondly, we strengthen the upper bound further and discuss consequences regarding the Chvátal-rank of subclasses of claw-free graphs.


A note on the cubical dimension of new classes of binary trees

Kamal Kabyl, Abdelhafid Berrachedi, Éric Sopena (2015)

Czechoslovak Mathematical Journal

The cubical dimension of a graph G is the smallest dimension of a hypercube into which G is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with 2 n vertices, n ≥ 1 , is n . The 2-rooted complete binary tree of depth n is obtained from two copies of the complete binary tree of depth n by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted...

A note on the domination number of a graph and its complement

Dănuţ Marcu (2001)

Mathematica Bohemica

If G is a simple graph of size n without isolated vertices and G ¯ is its complement, we show that the domination numbers of G and G ¯ satisfy γ ( G ) + γ ( G ¯ ) ≤ n - δ + 2 if γ ( G ) > 3 , δ + 3 if γ ( G ¯ ) > 3 , where δ is the minimum degree of vertices in G .

Currently displaying 301 – 320 of 5365