Large minimal irregular digraphs

• Autorzy: Dziechcińska-Halamoda Z. , Majcher Z. , Michael J. , Skupień Z.
• Języki publikacji: EN

Abstrakty

EN

A digraph is called irregular if its distinct vertices have distinct degree pairs. An irregular digraph is called minimal if the removal of any arc results in a non-irregular digraph. A large minimal irregular digraph Fn of order n is constructed if n is the sum of initial positive integers. It is easily seen that the minimum and maximum sizes among n-vertex irregular digraphs are asymptotic to [formula] and n2, respectively. It appears that the size of Fn is asymptotic to n2, too. Similarly, a minimal irregular oriented graph Hn is constructed such that the size of Hn is asymptotic to 1/2n2 whence it is asymptotically the largest size among n-vertex oriented graphs whether irregular or not.

Słowa kluczowe

EN

digraph; irregular digraph; oriented graph; minimal

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2003
• Tom: Vol. 23
• Strony: 21--24
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Dziechcińska-Halamoda Z.

• Institute of Mathematics and Informatics, University of Opole, Opole, Poland

autor

Majcher Z.

• Institute of Mathematics and Informatics, University of Opole, Opole, Poland

autor

Michael J.

• Institute of Mathematics and Informatics, University of Opole, Opole, Poland

autor

Skupień Z.

• Faculty of Appied Mathematics, AGH University of Science and Technology, Krakow, Poland

Bibliografia

• [1] Chartrand G., Lesniak L.: Graphs & Digraphs. Chapman & Hall, Third edition 1996
• [2] Dziechcińska-Halamoda Z., Majcher Z., Michael J., Skupień Z.: On extremum irregular oriented graphs, in preparation
• [3] Gargano M., Kennedy J.W., Quintas L. V.: Irregular digraphs. Congressus Numerantium, 72 (1990) 223-231
• [4] Górska J., Skupień Z., Majcher Z., Michael J.: A smallest irregular oriented graph containing a given diregular one. Discrete Math., to appear
• [5] Majcher Z., Michael J., Górska J., Skupień Z.: The minimum size of fully irregular oriented graphs. Discrete Math., 236 (2001) 263-272
• [6] Skupień Z.: Problems on fully irregular digraphs, [in:] Skupień Z. and Kalinowski R., guest eds., Discuss. Math. Graph Theory, 19, No 2 (1999) 253-25