کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653605 1632783 2014 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The (revised) Szeged index and the Wiener index of a nonbipartite graph
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The (revised) Szeged index and the Wiener index of a nonbipartite graph
چکیده انگلیسی

Hansen et al. used the computer program AutoGraphiX to study the differences between the Szeged index Sz(G)Sz(G) and the Wiener index W(G)W(G), and between the revised Szeged index Sz∗(G)Sz∗(G) and the Wiener index for a connected graph GG. They conjectured that for a connected nonbipartite graph GG with n≥5n≥5 vertices and girth g≥5g≥5, Sz(G)−W(G)≥2n−5Sz(G)−W(G)≥2n−5, and moreover, the bound is best possible when the graph is composed of a cycle C5C5 on 55 vertices and a tree TT on n−4n−4 vertices sharing a single vertex. They also conjectured that for a connected nonbipartite graph GG with n≥4n≥4 vertices, Sz∗(G)−W(G)≥n2+4n−64, and moreover, the bound is best possible when the graph is composed of a cycle C3C3 on 33 vertices and a tree TT on n−2n−2 vertices sharing a single vertex. In this paper, we not only give confirmative proofs to these two conjectures but also characterize those graphs that achieve the two lower bounds.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 36, February 2014, Pages 237–246
نویسندگان
, , ,