یک یادآوری در مورد تعداد درختان پوشا از گراف های جهت دار خط

A note on the number of spanning trees of line digraphs

مجله الزویر – Elsevier

سال ۲۰۱۵

چکیده

در نظر بگیرید که G یک گراف جهت دار و LG گراف جهت دار خط آن است. Levine یک فرمول را ارائه داد که تعداد درختان پوشای ریشه دار از LG و تعداد درختان پوشای ریشه دار G را مرتبط می کند، با این محدودیت که G منبع ندارد. در این یادآوری ، ما نشان می دهیم که این محدودیت می تواند برداشته شود و در نتیجه فرمول او برای تمام گراف های جهت دار برقرار است.

Abstract
Let G be a digraph and LG be its line digraph. Levine gave a formula that relates the number of rooted spanning trees of LG and that of G, with the restriction that G has no sources. In this note, we show that this restriction can be removed, thus his formula holds for all digraphs.

دانلود رایگان مقاله انگلیسی

خرید ترجمه آماده ورد