ให้ J เป็นคลาสของกราฟหรือคลาสของกราฟย่อยของกราฟหนึ่ง ถ้ามีการแปลงที่กำหนดรูปแบบคงที่ของสมาชิกหนึ่งใน J ไปยังอีกสมาชิกหนึ่งแล้ว เราจะเรียกว่าการแปลงกราฟบน J ซึ่งกล่าวได้ว่า การแปลงกราฟเป็นความสัมพันธ์ ρ จาก J ไปยัง Jนั่นคือ ρ ⊆ J ×J ให้ ρ เป็นการแปลงกราฟบน J เราสามารถนิยาม the ρ–graphเป็นกราฟที่มีเซตของจุดคือ J และมีเส้นเชื่อมระหว่างจุด 2 จุดคือกราฟ G และ H ถ้า (G,H) ∈ ρ ถ้า ρ ไม่มีสมบัติสะท้อนและมีสมบัติสมมาตรแล้ว the ρ– graph เป็นกราฟเชิงเดียว ดังนั้น การแปลงกราฟสามารถสร้างได้จากกราฟใน 2 ลักษณะคือ 1. จากคลาสของกราฟ หรือ 2. จากคลาสของกราฟย่อยของกราฟที่กำหนดให้ ฮารารี (1983) แนะนำการแปลงกราฟแบบหนึ่งที่เรียกว่า “การแลกเปลี่ยนเส้น”ให้ G เป็นกราฟเชื่อมโยงที่มีขนาด n ≥ 3 the tree graph T(G) ของ G ถูกกำหนดโดยให้ V(T(G)) เป็นเซตของกราฟต้นไม้แผ่ทั่วที่แตกต่างกันทั้งหมดของ G และจุด 2 จุด T1 ,T2 ∈ V(T(G)) ประชิดกันใน the tree graph T(G) ก็ต่อเมื่อ T1 และ T2 มีจำนวนเส้น n – 2 เส้นเท่านั้นที่ใช้ร่วมกัน the tree graph T(G) นี้เป็นตัวอย่างหนึ่งของ ρ–graph ที่เป็นกราฟเชิงเดียว ให้ G เป็นกราฟหนึ่ง สำหรับจุด a, b, c, d ที่แตกต่างกันใน V(G) ให้ ab และ cd เป็นเส้นใน G โดยที่ ac และ bd ไม่เป็นเส้นใน G กำหนดให้ Gσ(a, b : c, d) หรือเขียนอย่างง่ายคือ Gσ เป็นกราฟที่ได้จาก G โดยการตัดเส้น ab และ cd ออกและเพิ่มเส้น acและ bd การแปลง σ(a, b : c, d) ถูกเรียกว่า การดำเนินการสลับเส้น ให้ d คือลำดับดีกรีเชิงกราฟและให้ ℝ(d) และ ℂℝ(d) คือเซตของ realizations และ realizations เชื่อมโยงของ d ตามลำดับ โดยที่ σ เป็นการแปลงที่คงสภาพดีกรี ดังนั้นเราสามารถให้นิยามของ Σ(d) ว่าเป็นความสัมพันธ์บน ℝ(d) ที่กำหนดโดย (G, H) ∈Σ(d) ถ้า G ≇ H และมี การดำเนินการสลับเส้น σ บน G ที่ซึ่ง H = Gσ จะเห็นได้ชัดว่า σ(a, b : c, d) แจ่มชัดบน G ก็ต่อเมื่อ σ(a, c : b, d) แจ่มชัดบน Gσ(a, b : c, d) ดังนั้น Σ(d)–graph เป็นกราฟเชิงเดียว ในปี 1981 เทเลอร์ได้ พิสูจน์ว่า Σ(d)–graph เป็นกราฟเชื่อมโยง และหนึ่งปีต่อมา เขาก็ได้พิสูจน์อีกว่ากราฟย่อยของ Σ(d)–graph ที่อินดิวซ์โดยℂℝ(d) เป็นกราฟเชื่อมโยง สำหรับจำนวนเต็มบวก m และ n ซึ่ง 0 ≤ m ≤ (2n) ให้G(m, n) และ ℂG(m, n) เป็นเซตของกราฟและกราฟเชื่อมโยงทั้งหมดตามลำดับที่มีอันดับn และขนาด m ให้ G ∈ G (m, n) ซึ่ง e ∈ E(G) และ f ∉ E(G) กำหนดให้ Gt(e, f) เป็นกราฟที่ V(Gt(e, f) ) = V(G) และ E(Gt(e, f) ) = E(G – e + f) เราเรียกการแปลง t(e, f) ว่า jumping transformation ให้ T(m, n) คือความสัมพันธ์บน G(m, n) กำหนดโดย (G,H) ∈ T(m, n) ถ้า G ≇ H และ H ได้มาจาก G โดย jumping ransformationเนื่องจาก T(m, n) มีสมบัติสมมาตร ดังนั้นจึงได้ว่า T(m, n)–graph เป็นกราฟเชิงเดียว เราได้พิสูจน์มาแล้วว่า T(m, n)–graph และกราฟย่อยของ T(m, n)–graph ที่อินดิวซ์โดย ℂG(m, n) เป็นกราฟเชื่อมโยง ให้ G เป็นคลาสของกราฟทั้งหมด เราเรียกฟังก์ชัน π : G → ℤ ว่า กราฟพารามิเตอร์ ถ้า π(G) = π(H) สำหรับกราฟ G และ H ที่ไอโซมอฟิกกันทั้งหมดและเรียกกราฟพารามิเตอร์ π ว่ากราฟพารามิเตอร์ที่ปรากฏค่าทุกค่าเหนือ J ⊆ G ถ้ามีจำนวนเต็ม x และ y ที่ซึ่ง {π(G) : G ∈ J } = { k ∈ ℤ : x ≤ k ≤ y} เรากล่าวถึงผลงานที่เกี่ยวกับสมบัติการปรากฏค่าทุกค่าของกราฟพารามิเตอร์ต่อไปนี้ χ = จำนวนโครมาติก ω = จำนวนคลีก f = จำนวนฟอร์เรส φ = จำนวนดีไซคลิง α0 = จำนวนจุดอิสระ α1 = จำนวนการจับคู่ β0= จำนวนจุดปกคลุม β1 = จำนวนเส้นปกคลุม γ = จำนวนโดมิเนชัน γ = จำนวนโดมิเนชันของเส้น ถ้า π คือกราฟพารามิเตอร์เหนือ J แล้ว { π(G) : G ∈ J } ถูกกำหนดโดย min(π, J) := min{π(G) : G ∈ J } และ max(π, J) := max {π(G) : G ∈ J } ปัญหาของการหาค่า min(π, J) และ max(π, J) เราเรียกว่า ปัญหาค่าสุดขีดใน ทฤษฎีกราฟ เรากล่าวถึงผลงานที่เกี่ยวกับปัญหาค่าสุดขีดบนกราฟพารามิเตอร์ Let Ј be a class of graphs or subgraphs of a graph. If there is a fixed type of transformation of a member of Ј into another, then this will provide a definition of a graph transformation on Ј. Equivalently, a graph transformation may be defined as a relation ρ from Ј to Ј. In other words, ρ  Ј*Ј. Let ρ be a graph transformation on Ј. We can define the ρ –graph having Ј as its vertex set and there is an edge between two vertices G and H if (G,H)  ρ. If ρ is an irreflexive and symmetric, then the _-graph is simple. Thus the ρ -graph arises from graphs in at least two different ways: 1. from a class of graphs, or 2. from a class of subgraphs of a fixed graph. Harary(1983) introduced a graph transformation and called it an edge exchange as follows: Let G be a connected graph of order n  3. The tree graph, T(G), of G is defined by specifying V (T(G)) to be the set of all distinct spanning trees of G, and two vertices T1, T2 2 V (T(G)) are adjacent in T(G) if and only if T1 and T2 have exactly n − 2 edges in common. This is an example of an undirected ρ - graph. Let G be a graph. For the distinct vertices a, b, c, and d in V (G), let ab and cd be edges in G, given that ac and bd are not edges in G. DefineG (a,b;c,d), simply written G, to be the graph obtained from G by deleting the edges ab and cd and adding the edges ac and bd. The transformation  (a, b; c, d) is called a switching operation. Let d be a graphic degree sequence. Let R(d) and CR(d) be the sets of realizations and connected realizations of d, respectively. Since  is a degree preserving transformation, it is reasonable to define (d) as a relation on R(d) as (G,H) (d) if G ≠ H and there is a switching  on G such that H = G  It is easy to see that  (a, b; c, d) is well-defined on G if and only if  (a, c; b, d) is well-defined on G  (a,b;c,d). Thus the (d)-graph is simple. The (d)-graph was proved to be connected by Taylor in 1981. One year later, it was also proved by Taylor that the subgraph of (d)-graph induced by CR(d) is connected. For positive integers m and m with 0  m  (2n), let G(m, n) and CG(m, n) be the sets of all graphs and connected graphs, respectively, of order n and size m. Let G  G(m, n) with e E (G) and  E (G). Define Gt(e,f ) to be a graph with V (Gt(e,f )) = V (G) and E(Gt(e,f )) = E (G − e + ). A transformation t(e, f) is called a jumping transformation. Now let T(m, n) be relation on G(m, n) defined by (G,H)  T (m, n) if G ≠ H and H can be obtained from G by a jumping transformation. Since T(m, n) is symmetric, it follows that T(m, n)-graph is simple. We proved recently that the T(m, n)-graph and the subgraph of T(m, n)-graph induced by CG(m, n) are connected. Let G be the class of all graphs. A function : G  Z is called a graph parameter if  (G) =  (H) for all isomorphic graphs G and H. A graph parameter _ is called an interpolation graph parameter over J  G if there exist integers  and γ such that { (G) : G  J} = {k  Z :  k y}. We reveiw our results on the interpolation properties of the following graph parameters:  = the chromatic number, ω= the clique number  = the forest number, Ø = the decycling number α0 = the independence number, α1 = the matching number β0 = the vertex covering number, β1 = the edge covering number γ= the domination number, ỳ = the edge domination number If  is an interpolation graph parameter over J, then {  (G) : G  J } is uniquely determined by min( ,J) := min{  (G) : G J } and max(, J) := max{  (G) : G  J}. The problem of finding min(,J) and max(,J) is called the extremal problem in graph theory. We also reveiw our results on extremal problem on graph parameters.