Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Opuscula Mathematica

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Extremal traceable graphs with non-traceable edges

Wojda A. P.

Opuscula Mathematica

2009

Vol. 29, no. 1

89-92

By NT(n) we denote the set of graphs of order n which are traceable but have non-traceable edges, i.e. edges which are not contained in any hamiltonian path. The class NT(re) has been considered by Balińska and co-authors in a paper published in 2003, where it was proved that the maximum size t(max)(n) of a graph in NT(n) is at least (n2-5n+14)/2 (for n≥ 12). The authors also found t(max)(n) for 5 ≤ n ≤ 11. We prove that, for n n≥ 5, t(max) (n) = max {(n-2/2) + 4, [formula] and, moreover, we characterize the extremal graphs (in fact we prove that these graphs are exactly those already described in the paper by Balińska et al). We also prove that a traceable graph of order n n≥ 5 may have at most [n-3/2] [n-3/2] non traceable edges (this result was conjectured in the mentioned paper by Balińska and co-authors).

Pm-saturated graphs with minimum size

Dudek A., Wojda A.P.

Opuscula Mathematica

2004

Vol. 24, no. 1

43-55

By Pm we denote a path of order m. A graph G is said to be Pm - saturated if G has no subgraph isomorphic to Pm and adding any new edge to G creates a Pm in G. In 1986 L. Kaszonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size sat(n; Pm) of Pm-saturated graph and characterize the graphs of Sat(n; Pm) - the set of Pm-saturated graphs of minimum size. They have solved this problem for [formula].