Labeled Embedding Of (n, n-2)-Graphs In Their Complements

• Autorzy: M.-A. Tahraoui , E. Duchêne , H. Kheddouci
• Języki publikacji: EN

Abstrakty

EN

Graph packing generally deals with unlabeled graphs. In [4], the authors have introduced a new variant of the graph packing problem, called the labeled packing of a graph. This problem has recently been studied on trees [M.A. Tahraoui, E. Duchêne and H. Kheddouci, Labeled 2-packings of trees, Discrete Math. 338 (2015) 816-824] and cycles [E. Duchˆene, H. Kheddouci, R.J. Nowakowski and M.A. Tahraoui, Labeled packing of graphs, Australas. J. Combin. 57 (2013) 109-126]. In this note, we present a lower bound on the labeled packing number of any (n, n − 2)-graph into Kn. This result improves the bound given by Woźniak in [Embedding graphs of small size, Discrete Appl. Math. 51 (1994) 233-241].

Słowa kluczowe

EN

packing of graphs; labeled packing; permutation

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 4
• Strony: 1015-1025

Daty

wydano

2017-11-27

otrzymano

2015-09-11

poprawiono

2016-07-06

zaakceptowano

2016-08-23

online

2017-09-02

Twórcy

autor

M.-A. Tahraoui

• , 1, LIRIS UMR5205, F-69622,

autor

E. Duchêne

• , 1, LIRIS UMR5205, F-69622,

autor

H. Kheddouci

• , 1, LIRIS UMR5205, F-69622,

Identyfikatory

DOI

10.7151/dmgt.1977