Skip to main content
SUPERVISOR
Gholamreza Omidi,Behnaz Omoomi
غلامرضا امیدی اردلی (استاد راهنما) بهناز عمومی (استاد مشاور)
 
STUDENT
Fatemeh Khatami
فاطمه خاتمی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1386

TITLE

Tutte Conjecture’s on Some Families of Graphs
In this thesis we investigate the concepts of nowhere-zero flow and connectivity of graphs. A nowhere-zero k-flow in a graph G corresponds to assigning an orientation to the edges of G as well as integers {±1, . . . ,±(k ? 1)} to the edges such that for every vertex, the sum of the values on incoming edges equals to the sum on the outgoing ones. In the middle of twentieth century, this concept was introduced by Tutte. The main problem regarding nowhere-zero flows is to find the minimum value of k such that a given graph admits a nowhere-zero k-flow. To do this, Tutte has introduced three main conjectures among which Tutte’s 3-flow conjecture implies that every 4-edge connected graph admits a nowhere-zero 3-flow. The aim of this thesis is studying the accuracy of Tutte’s conjectures, (in particular the 3-flow conjecture for special families of graphs). To do so, triangularly-connected graphs and abelian Cayley graphs which admit a nowhere-zero 3-flow are characterized. Particularly, it is shown that 3-flow conjecture ...These products include Cartesian, Tensor, strong and lexicographic products. The Cartesian product of every pair of graphs G and H admits a nowhere-zero 3-flow unless G is odd-circuit tree and H has a bridge. In the case of Tensor product of graphs, for two graphs G and H with _ _ 2 and H not belonging to a well-characterized Strong (also lexicographic) product admits a nowhere-zero 3-flow if and only if not equal product a tree and P2. In 1992, Jaeger et al. introduced the concept of group connectivity of graphs, as an extension of nowhere-zero flows. For an abelian group A, let b : V (G) ! A such that Pv2V (G) b(v) = 0. b is called a sum-zero function. In this case, a (A, b)?nowhere zero flow in graph G is defined as an assignment of a direction to E(G) and as well as an element A{0} to E(G) such that Pv2E+(v) f(e) ? Pv2E?(v) f(e) = b(v), for every v 2 V (G). For b = 0, every (A, b)?nowhere zero flow is a A-nowhere zero flow. A graph G is called A-connected when for every sum-zero function b, there is a (A, b)?nowhere zero flow. Hence the concept of A-connected generalization of concept of nowhere-zero flow. The accuracy of Tutte’s conjectures for specific families of graphs can be obtained by using this concept. In the sequel, through studying the concept group connectivity of graphs, some results on nowhere-zero flows in some graphs including regular, strongly regular graphs and graphs with diameter at most 2 are obtained and it is shown that each strongly regular graph with girth 3 admits a nowhere-zero 3-flow. In case of graphs with diameter at most 2, Lai proofed that for every abelian group A with |A| _ 6, G is A-connected.
در این پا یان‌نامه به بررسی دو مفهوم جریان همه‌جا ناصفر و همبندی گروهی گراف‌ها پرداخته می‌شود. یک k-جریان همه‌جا ناصفر روی گراف G ، عبارتست از اختصاص یک جهت‌دهی به یال‌های G و تخصیص اعداد صحیح به یال‌ها به‌طوری که در هر رأس، مجموع اعداد وابسته به یال‌های خروجی برابر با مجموع اعداد وابسته به یال‌های ورودی باشد. این مفهوم توسط تات در اواسط قرن بیستم، وارد نظریه‌ی گراف شد. مسأله‌ی اصلی در ارتباط با وجود جریان‌های همه‌جا ناصفر روی گراف‌ها، یافتن کوچکترین مقدار k ای است که گراف دارای یک k-جریان همه‌جا ناصفر باشد. در این ارتباط، تات سه حدس مهم مطرح نموده است. از جمله، حدس 3-جریان تات بیان می‌کند که هر گراف 4-یال همبند یک 3-جریان همه جا ناصفر دارد. هدف این پایان‌نامه، مطالعه‌ی درستی حدس‌های تات به‌خصوص حدس 3-جریان برای خانواده‌های خاص از گراف‌ها می‌باشد. بدین منظور، گراف‌های مثلث-همبند و گراف‌های کیلی وابسته به گروه‌های آبلی که دارای 3-جریان همه‌جا ناصفر هستند، رده‌بندی شده‌اند. به‌علاوه، جریان‌های همه‌جا ناصفر روی حاصل‌ضرب‌هایی از گراف‌ها نیز مورد بررسی قرار گرفته است. در سال 1992، جاگر و دیگران تعمیمی از مفهوم جریان‌های همه‌جا ناصفر تحت عنوان همبندی گروهی گراف‌ها را معرفی کردند. با استفاده از این مفهوم می‌توان درستی حدس‌های تات را برای خانواده‌های خاصی از گراف‌ها بررسی نمود. در ادامه همبندی گروهی گراف‌ها مطالعه شده و با کمک آن نتایجی در مورد جریان‌های همه‌جا ناصفر روی برخی از گراف‌ها از جمله گراف‌های منظم، قویاً منظم و گراف‌های با قطر حداکثر 2 به‌دست آورده شده است.

ارتقاء امنیت وب با وف بومی