𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On strongly asymmetric graphs

✍ Scribed by Mirko Lepović

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
261 KB
Volume
145
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be an arbitrary simple graph of order n. G is called strongly asymmetric if all induced overgraphs of G of order (n + 1) are nonisomorphic. In this paper we give some properties of such graphs and prove that the class 6ec of all connected strongly asymmetric graphs is infinite.

In this paper we consider only finite graphs having no loops or multiple edges. The vertex set of a graph G is denoted by V(G), and its order (number of vertices) by IGI. The edge set of G is denoted by E(G), and its number of edges by IE(G)b.

Let S be any (possibly empty) subset of the vertex set V(G). Denote by Gs the graph obtained from the graph G by adding a new vertex x(x q~ V(G)), which is adjacent exactly to the vertices from S. Graph G is obviously an induced subgraph of the graph Gs, and Gs is an induced overgraph of G. Varying the set S ~ V(G) we get 2161 such graphs Gs. The family of all such graphs is denoted by Cg(G). We shall briefly call (~(G) the overset of G. We say that fg(G) is connected if every graph Hef#(G) except G o so is. It is easily seen that this happens if and only if the graph G is connected.

We now introduce the following definition.

📜 SIMILAR VOLUMES

On strongly regular self - complementary
On strongly regular self - complementary graphs
✍ Sergio Ruiz 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB 👁 1 views

## Abstract It is shown that certain conditions assumed on a regular self‐complementary graph are not sufficient for the graph to be strongly regular, answering in the negative a question posed by Kotzig in [1].

Strongly indexable graphs
Strongly indexable graphs
✍ B.D. Acharya; S.M. Hegde 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 633 KB

Acharya, B.D. and S.M. Hegde, Strongly indexable graphs, Discrete Mathematics 93 (1991) 123-129. A (p, q)-graph G = (V, E) is said to be strongly k-indexable if it admits a strong k-indexer viz., an injective function f : V -{C, 1, 2, . . . , p -1) such that f(x)+f(y)=f+(xy)Ef+(E)={k,k+l,k+2,.. . ,

Strongly graceful graphs
Strongly graceful graphs
✍ Maryvonne Maheo 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 731 KB

In this paper, we prove that the n-cube is graceful, thus answering a conjecture of J.-C. Bermond and Gangopadhyay and Rao Hebbare. To do that, we introduce a special kind of graceful numbering, particular case of a-valuation, called strongly graceful and we prove that if a graph G is strongly grace

Strongly balanced graphs and random grap
Strongly balanced graphs and random graphs
✍ Andrzej Ruciński; Andrew Vince 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 455 KB

The concept of strongly balanced graph is introduced. It is shown that there exists a strongly balanced graph with u vertices and e edges if and only if I s u -1 s e s ( 2 " ) . This result is applied to a classic question of Erdos and Renyi: What is the probability that a random graph on n vertices

On strongly almost trivial embeddings of
On strongly almost trivial embeddings of graphs
✍ Ryo Hanaki 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB

## Abstract We present four new classes of graphs, two of which every member has a strongly almost trivial embedding, and the other two of which every member has no strongly almost trivial embeddings. We show that the property that a graph has a strongly almost trivial embedding and the property th