α-size of Trees with Maximum Degree Three and Perfect Matching

L Brankovic; Craig Murch; Jeffrey Pond; A Rosa

α-size of Trees with Maximum Degree Three and Perfect Matching

L Brankovic
, Craig Murch
, Jeffrey Pond
, A Rosa

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In this paper we provide a lower bound for the alpha-size of trees with maximum degree three and a perfect matching as a function of a lower bound for minimum order of such a tree that does not have an alpha-labelling. By using a computer search we show that all such trees on less than 30 vertices have an α-labelling. This brings the lower bound for the alpha-size to 14n/15, for such trees of order n. Finally, we conjecture that all trees with maximum degree three and a perfect matching have an α-labelling.

Original language	English
Title of host publication	Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)
Editors	Joe Ryan, Prabhu Manyem, Kiki Sugeng, Mirka Miller
Place of Publication	Ballarat, Australia
Publisher	University of Ballarat
Pages	47-56
ISBN (Print)	0646452525
Publication status	Published - 30 Sept 2005
Event	AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms - University of Ballarat, Ballarat, Australia Duration: 18 Sept 2005 → 21 Sept 2005

Conference

Conference	AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms
City	Ballarat, Australia
Period	18/09/05 → 21/09/05

Access to Document

https://hdl.handle.net/1959.11/63404

Handle.net

Persistent link

Cite this

@inproceedings{f13af8f8e2494e9baec7f0d877ac6d8a,

title = "α-size of Trees with Maximum Degree Three and Perfect Matching",

abstract = "In this paper we provide a lower bound for the alpha-size of trees with maximum degree three and a perfect matching as a function of a lower bound for minimum order of such a tree that does not have an alpha-labelling. By using a computer search we show that all such trees on less than 30 vertices have an α-labelling. This brings the lower bound for the alpha-size to 14n/15, for such trees of order n. Finally, we conjecture that all trees with maximum degree three and a perfect matching have an α-labelling.",

author = "L Brankovic and Craig Murch and Jeffrey Pond and A Rosa",

year = "2005",

month = sep,

day = "30",

language = "English",

isbn = "0646452525",

pages = "47--56",

editor = "Joe Ryan and Prabhu Manyem and Kiki Sugeng and Mirka Miller",

booktitle = "Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)",

publisher = "University of Ballarat",

note = "AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms ; Conference date: 18-09-2005 Through 21-09-2005",

}

Brankovic, L, Murch, C, Pond, J & Rosa, A 2005, α-size of Trees with Maximum Degree Three and Perfect Matching. in J Ryan, P Manyem, K Sugeng & M Miller (eds), Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005). University of Ballarat, Ballarat, Australia, pp. 47-56, AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms, Ballarat, Australia, 18/09/05. <https://hdl.handle.net/1959.11/63404>

α-size of Trees with Maximum Degree Three and Perfect Matching. / Brankovic, L; Murch, Craig; Pond, Jeffrey et al.
Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005). ed. / Joe Ryan; Prabhu Manyem; Kiki Sugeng; Mirka Miller. Ballarat, Australia: University of Ballarat, 2005. p. 47-56.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - α-size of Trees with Maximum Degree Three and Perfect Matching

AU - Brankovic, L

AU - Murch, Craig

AU - Pond, Jeffrey

AU - Rosa, A

PY - 2005/9/30

Y1 - 2005/9/30

N2 - In this paper we provide a lower bound for the alpha-size of trees with maximum degree three and a perfect matching as a function of a lower bound for minimum order of such a tree that does not have an alpha-labelling. By using a computer search we show that all such trees on less than 30 vertices have an α-labelling. This brings the lower bound for the alpha-size to 14n/15, for such trees of order n. Finally, we conjecture that all trees with maximum degree three and a perfect matching have an α-labelling.

AB - In this paper we provide a lower bound for the alpha-size of trees with maximum degree three and a perfect matching as a function of a lower bound for minimum order of such a tree that does not have an alpha-labelling. By using a computer search we show that all such trees on less than 30 vertices have an α-labelling. This brings the lower bound for the alpha-size to 14n/15, for such trees of order n. Finally, we conjecture that all trees with maximum degree three and a perfect matching have an α-labelling.

M3 - Conference contribution

SN - 0646452525

SP - 47

EP - 56

BT - Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)

A2 - Ryan, Joe

A2 - Manyem, Prabhu

A2 - Sugeng, Kiki

A2 - Miller, Mirka

PB - University of Ballarat

CY - Ballarat, Australia

T2 - AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms

Y2 - 18 September 2005 through 21 September 2005

ER -

α-size of Trees with Maximum Degree Three and Perfect Matching

Abstract

Conference

Access to Document

Handle.net

Fingerprint

Cite this