Graph Theory

63 flashcards · Other · by Bahar Hashemi

  1. δ(G)>=t\delta(G) >= tδ(G)>=t and G has a perfect matching. how many perfect matchings it have?

  2. DEF: r-factorable

  3. Petersen's theorem

  4. DEF: [a, b]-factor

  5. DEF: {a, b}-factor

  6. THOMASSEN'S THEOREM

  7. NECCESSARY SUFFICIENT CONDITION TO HAVE {1, 2}-FACTOR

  8. k regular graphs have {1, 2}-factor or [1, 2]-factor?

  9. necessary sufficient conditions for ∀v∈V(G)\forall v \in V(G)∀v∈V(G) G \ v has a {1, 2}-factor

  10. Star factor theorem

  11. DEF: Per(A)

  12. Per(A) ? ∣{1,2}−factor(G)∣Per(A) \,?\, |\{1,2\}-factor(G)|Per(A)?∣{1,2}−factor(G)∣

    Per(A)≥∣{1,2}−factor(G)∣Per(A) \geq |\{1,2\}-factor(G)|Per(A)≥∣{1,2}−factor(G)∣

  13. DEF Permat(G)

  14. Permat(bipartite)?

  15. Minc's theorem

  16. Alon-Friedland theorem

  17. Per(Directed graph)?

  18. Birkhof's Theorem

  19. necessary sufficient condition to have directed 2-factor

  20. necessary sufficient condition to have directed path-factor

    i(G\S)<=2∣S∣i(G\S) <= 2|S|i(G\S)<=2∣S∣

  21. Star factor theorem

  22. r-extendable

  23. Little-Grant-Holton's theorem necessary sufficient condition for G to be 1-extendable

    O(G\S)≤∣S∣−2O(G\S) \leq |S| - 2O(G\S)≤∣S∣−2

  24. Little-Grant-Holton's theorem necessary sufficient condition for G to be r-extendable

  25. Babler's Theorem on 1-extendability of r-regular graphs

  26. having 2-factor in regular graphs

  27. DEF: factor critical

  28. Lovasz theorem on even-factors

  29. DEF: super eulerian

  30. cubic graphs having a triangle-free 2-factor

  31. 4 regular graphs having a triangle free 2-factor

  32. Plesnik's theorem on having perfect matchings

  33. Sumner's theorem on having perfect matching

  34. tutte-berge theorem

  35. Edmond-Gallai's theorem

  36. DEF: H | G

  37. DEF: prime graph

  38. Graceful labeling

  39. graceful trees decomposition

    شماره دهی می کنیم گراف کاملو

  40. what can be decomposed into linear forests?

    می دونیم k_(2k - 1)

  41. κ(G)\kappa (G)κ(G) and κ′(G)\kappa'(G)κ′(G) relation

  42. κ(G)\kappa(G)κ(G) and κ′(G)\kappa'(G) κ′(G) in subcubic graphs

  43. Mader's theorem

  44. stronger than mader

  46. whitney's theorem

  47. on contraction and 2 connectedness

  48. when a graph has a strong directioning?

    when it is 2-edge connected

  49. on contraction and 3 connectedness

  50. قضیه ساختاری تات برای گراف های 3 همبند

  51. قضیه ساختاری گراف های عامل بحرانی

  52. DEF: تجزیه گوشی فرد

  53. necessary sufficient condition for G/xyG/xyG/xy to be k - edge connected

  54. DEF separation

  55. Menger's theorem

  56. necessary sufficient conditions for G to be k-connected (Menger's result)

  57. upper bounds on path covers connected components

  58. Gallai-Milgram theorem on path covers of directed graphs

  59. dilworse theorem

  60. sperner lemma

  61. erdos - szekers

  62. شرط لازم و کافی برای دنباله امتیازی بودن

    این پایینی غلطه باید بیشتر مساوی باشه و اینا :)

  63. necessary conditions for graphic sequences