Lower bound for the size of maximal nontraceable graphs

Details Lower bound for the size of maximal nontraceable graphs Lower bound for the size of maximal nontraceable graphs

2004-07-16

arxiv.org/abs/math/0407292v1

Mathematics

Combinatorics

10 pages, 3 figures

Scientific paper

Let g(n) denote the minimum number of edges of a maximal nontraceable graph of order n. Dudek, Katona and Wojda (2003) showed that g(n)\geq\ceil{(3n-2)/2}-2 for n\geq 20 and g(n)\leq\ceil{(3n-2)/2} for n\geq 54 as well as for n\in I={22,23,30,31,38,39, 40,41,42,43,46,47,48,49,50,51}. We show that g(n)=\ceil{(3n-2)/2} for n\geq 54 as well as for n\in I\cup{12,13} and we determine g(n) for n\leq 9.

Affiliated with

Also associated with

No associations

Rating

Lower bound for the size of maximal nontraceable graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower bound for the size of maximal nontraceable graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower bound for the size of maximal nontraceable graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636491