✦ LIBER ✦

Orbits on vertices and edges of finite graphs

✍ Scribed by Dominique Buset

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 134 KB
Volume: 57
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(85)90181-5

No coin nor oath required. For personal study only.

✦ Synopsis

Given two integers v > 0 and e/> 0, we prove that there exists a finite graph (resp. a finite connected graph) whose automorphism group has exactly v orbits on the set of vertices and e orbits on the set of edges if and only if v ~< 2e + 1 (resp. v ~< e + 1).

📜 SIMILAR VOLUMES

Bounds on the eigenvalues of graphs with

Bounds on the eigenvalues of graphs with cut vertices or edges

✍ Bao-Xuan Zhu 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 325 KB

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n ver

New Constructions of Bipartite Graphs on

New Constructions of Bipartite Graphs on m, n Vertices with Many Edges and Without Small Cycles

✍ F. Lazebnik; V.A. Ustimenko; A.J. Woldar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 293 KB

On eccentric vertices in graphs

✍ Chartrand, Gary; Schultz, Michelle; Winters, Steven J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 387 KB

The eccentricity e(u) of a vertex u in a connected graph G is the distance between u and a vertex furthest from u. The minimum eccentricity among the vertices of G is the radius rad G of G, and the maximum The radial number m(u) of u is the minimum eccentricity among the eccentric vertices of u, wh

Extremal problems involving vertices and

Extremal problems involving vertices and edges on odd cycles

✍ P. Erdős; R.J. Faudree; C.C. Rousseau 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 603 KB

Erdiis, P., R.J. Faudree and C.C. Rousseau, Extremal problems involving vertices and edges on odd cycles, Discrete Mathematics 101 (1992) 23-31. We investigate the minimum, taken over all graphs G with n vertices and at least [n\*/4] + 1 edges, of the number of vertices and edges of G which are on c

Maximum number of edges joining vertices

Maximum number of edges joining vertices on a cube

✍ Khaled A.S. Abdel-Ghaffar 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 84 KB

Let E d (n) be the number of edges joining vertices from a set of n vertices on a d-dimensional cube, maximized over all such sets. We show that E d (n) = r-1 i=0 (l i /2 + i)2 l i , where r and l 0 > l 1 > • • • > l r-1 are nonnegative integers defined by n = r-1 i=0 2 l i .

On Graphs Without Multicliqual Edges

✍ Lim Chong-Keang; Peng Yee-Hock 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 418 KB

## Abstract An edge which belongs to more than one clique of a given graph is called a multicliqual edge. We find a necessary and sufficient condition for a graph __H__ to be the clique graph of some graph __G__ without multicliqual edges. We also give a characterization of graphs without multicliq