GRAPHS COMPLEMENTS

Vol. (1978)335-338

FIXED-POINT-FREE EMBEDDINGS OF GRAPHS IN THEIR COMPLEMENTS

SEYMOUR SCHUSTER

Carleton College

Northfield, Minnesota 55057 U.S.A.

(Received January 20, 1978)

ABSTRACT. The following is proved: If G is a labeled (p,p-2) graph where p ^> 2, then there exists an isomorphic embedding of G in its complement G such that has no fixed vertices. The extension to (p,p-l) graphs is also considered.

IiEY WORDS AND PHRASES. Labeled graph, complement, and embedding.

AMS(MOS) SUBJECT CLASSIFICATION (1970) CODE. Primary 05ClO.

If G is a graph, then V(G) and E(G) will denote its vertex set and edge set, respectively. Further, G is called a (p,q) graph if

IV(G)

^{p and}

E(G) q. An embedding of G in a graph H is an isomorphic mapping of G into H; in other words, there exists an embedding of G in H if H contains a subgraph which is an isomorphic copy of G.

The fact that every (p,p-2) graph G can be embedded in its complement G was proven, independently, in [i], [2], and [4]. In the present paper, we establish a strengthened version of this result and also consider exten-

336 S. SCHUSTER

sions. First of all, we assume that G is labeled; then it becomes meaningful to ask whether the embedding has fixed vertices. This question has perti- nence in the study of embedding (p,p-l) graphs in their complements. Indeed, the theorem we prove here serves as a useful tool in characterizing those

(p,p-l) graphs which are embeddable in their complements (see [3]).

THEOREM i. If G is a labeled (p,p-2) graph where p ^> 2, then there exists an isomorphic embedding of G in G such that has no fixed vertices.

PROOF. The proof ^is by induction.

The theorem is clearly true for p 2 and 3. We assume that it holds, also, for all (p,p-2) graphs where p < k and k ^> 4, and we consider G to be an arbitrary (k,k-2) graph. (N.B. This induction hypothesis implies that the theorem also holds for all (p,p-n) graphs, where n > 2, p ^< k and k ^> 4.)

First, we suppose that G has an isolated vertex v. Since G has k-2 edges, it must possess a vertex u of degree greater than one. Then G

I

G u,v} is a (k-2,k-n) graph, with n 4, so the induction hypothesis guar- antees the existence of an embedding

:

^G_I ^{+ G}_I ^{which maps no vertex of G}_I

onto itself. This embedding can be extended to an embedding of G in G by defining (u) --v and (v) ^u. It is clear that this extension, also, has no fixed vertices.

Henceforth, we assume that G has no isolated vertices.

Since every cyclic component ^having r vertices has at least r edges, the components of G must include at least two non-trlvial trees T

I ^{and T}2.

If one of these trees, say TI, ^{is of order} two, we write V(T

I) {Vl,V2}

^{and consider G}2 G- v

2, which is a (k-l,k-3) graph. The induction hypothesis guarantees a fixed-point-free embedding of G

2 ⁱⁿ G

2. ^{We define} G

-

^{G as follows: (v}

_{I) v2,}

^(v

₂₎

^o(v

_I),

^and

(v) (v) for all v E V(G), and v v

I.

With this definition, it is easy to see that is a fixed-point-free embedding of G inG.

If neither T

I ^{nor T}2 ^is of order two, we form the graph G

3 G- T I.

Let x e

V(TI)

^{be a vertex of degree at least two and y e V(G}

3)

also of degree at least two. Then the subgraphs T

1 x and G

3 y both satisfy the induction hypothesis. Let T

1 x ^/ T

1 x and 8 ^G₃ ^y

-

^G3 y be fixed-point- free embeddings. We define G ^/ G as follows:

(x) y, (y) x, (v) o(v) for all v e V(T I x) and (v) 8(v) for all v e V(G

3 y).

This produces a fixed-point-free embedding of G in its complement, thus completing the proof of the theorem.

The foregoing result is "best possible" in the sense that there exist (p,p-l) graphs which are embeddable in their complements, but which cannot be so embedded without fixed vertices. Two simple examples arise in consid- ering the disjoint union of a small star and a 3-cycle: viz.,

KI,

2 U C

3 and

KI,

3 U C

3. ^{However, it is} interesting to note that all other (p,p-l) graphs that are contained in their complements can be embedded without fixed vertices. By slight modifications of the arguments in [3], one can prove the following.

THEOREM 2. Let G be a labeled (p,p-l) graph such that (a) G is embed- dable in its complement and (b) G

KI,

2 U ^C₃ ^{and G} #

KI,

3

there exists a fixed-point-free embedding of G in G.

Then

This result can be stated more explicitly by defining the class of graphs to consist of K

I U ^C_4, ^KI U ^2C3,

Kl,p_

^{I, and}

Kl,n

^[2

C3

^{for n > 0}

(assuming the convention that

KI,

0

KI).

Then Theorem 2 says: If G be any labeled (p,p-l) graph, ^{then there is a} flxed-point-free embedding of G in G if and only if G

.

338 S. SCHUSTER

While Theorem l plays a role in the proof of further embedding theorems, Theorem 2 does not enjoy such significance; it seems not to possess anything beyond intrinsic interest. For this reason, primarily, we haven’t given more attention to the proof of Theorem 2. The interested reader should find little difficulty in constructing the fixed-point-free embeddings of (p,p-l) graphs from the proofs provided in [3].

ACKNOWLEDGEMENT. The author expresses his appreciation to the Mellon Founda- tion for a grant which partially supported his research during 1976-78.

REFERENCES

i. Bollobs, B. and S. E. Eldridgeo Packings of Graphs and Applications to Computational Complexity, Proceedings of the Fifth ^British Com- binatorial Conference (Aberdeen, 1975), Congressus Numerantium XV, Utilitas Mathematica Publishing.

2. Burns, D. and S. Schuster. Every (p,p-2) Graph ^is Contained in its Complement, Journal of Graph Theory i_. (1977) ^277-279.

3. Burns, D. and S. Schuster. Embedding (p,p-l) Graphs in Their Complements, Israel Journal of Mathematics (to appear).

4. Sauer, N. and J. Spencer. Edge Disjoint Placement of Graphs, Journal of Combinatorial Theory (B) (to appear).

Special Issue on

Intelligent Computational Methods for Financial Engineering

Call for Papers

As a multidisciplinary field, financial engineering is becom- ing increasingly important in today’s economic and financial world, especially in areas such as portfolio management, as- set valuation and prediction, fraud detection, and credit risk management. For example, in a credit risk context, the re- cently approved Basel II guidelines advise financial institu- tions to build comprehensible credit risk models in order to optimize their capital allocation policy. Computational methods are being intensively studied and applied to im- prove the quality of the financial decisions that need to be made. Until now, computational methods and models are central to the analysis of economic and financial decisions.

However, more and more researchers have found that the financial environment is not ruled by mathematical distribu- tions or statistical models. In such situations, some attempts have also been made to develop financial engineering mod- els using intelligent computing approaches. For example, an artificial neural network (ANN) is a nonparametric estima- tion technique which does not make any distributional as- sumptions regarding the underlying asset. Instead, ANN ap- proach develops a model using sets of unknown parameters and lets the optimization routine seek the best fitting pa- rameters to obtain the desired results. The main aim of this special issue is not to merely illustrate the superior perfor- mance of a new intelligent computational method, but also to demonstrate how it can be used effectively in a financial engineering environment to improve and facilitate financial decision making. In this sense, the submissions should es- pecially address how the results of estimated computational models (e.g., ANN, support vector machines, evolutionary algorithm, and fuzzy models) can be used to develop intelli- gent, easy-to-use, and/or comprehensible computational sys- tems (e.g., decision support systems, agent-based system, and web-based systems)

This special issue will include (but not be limited to) the following topics:

• Computational methods: artificial intelligence, neu- ral networks, evolutionary algorithms, fuzzy inference, hybrid learning, ensemble learning, cooperative learn- ing, multiagent learning

• Application fields: asset valuation and prediction, as- set allocation and portfolio selection, bankruptcy pre- diction, fraud detection, credit risk management

• Implementation aspects: decision support systems, expert systems, information systems, intelligent agents, web service, monitoring, deployment, imple- mentation

Authors should follow the Journal of Applied Mathemat- ics and Decision Sciences manuscript format described at the journal site http://www.hindawi.com/journals/jamds/.

Prospective authors should submit an electronic copy of their complete manuscript through the journal Manuscript Track- ing System athttp://mts.hindawi.com/, according to the fol- lowing timetable:

Manuscript Due December 1, 2008 First Round of Reviews March 1, 2009 Publication Date June 1, 2009

Guest Editors

Lean Yu,Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;

Department of Management Sciences, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong;

[email protected]

Shouyang Wang,Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; [email protected]

K. K. Lai,Department of Management Sciences, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong; [email protected]

Hindawi Publishing Corporation http://www.hindawi.com