ridm@nrct.go.th   ระบบคลังข้อมูลงานวิจัยไทย   รายการโปรดที่คุณเลือกไว้

On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs.

หน่วยงาน Nanyang Technological University, Singapore

รายละเอียด

ชื่อเรื่อง : On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs.
นักวิจัย : Klerk, Etienne de. , Newman, M. W. , Pasechnik, Dmitrii V. , Sotirov, R.
คำค้น : DRNTU::Science::Mathematics.
หน่วยงาน : Nanyang Technological University, Singapore
ผู้ร่วมงาน : -
ปีพิมพ์ : 2551
อ้างอิง : Klerk, E. D., Newman, M. W., Pasechnik, D. V. & Sotirov R. (2009). On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs. European Journal of Combinatorics, 30(4), 879–888 , http://hdl.handle.net/10220/7516 , http://dx.doi.org/10.1016/j.ejc.2008.07.022
ที่มา : -
ความเชี่ยวชาญ : -
ความสัมพันธ์ : European journal of combinatorics
ขอบเขตของเนื้อหา : -
บทคัดย่อ/คำอธิบาย :

We consider k-regular graphs with loops, and study the Lovász ϑ-numbers and Schrijver ϑ′-numbers of the graphs that result when the loop edges are removed. We show that the ϑ-number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newman. Eigenvalue bounds for independent sets, J. Combin. Theory B 98 (4) (2008) 721–734]. As an application we compute the ϑ and ϑ′ numbers of certain instances of Erdős–Rényi graphs. This computation exploits the graph symmetry using the methodology introduced in [E. de Klerk, D.V. Pasechnik and A. Schrijver, Reduction of symmetric semidefinite programs using the regular *-representation, Math. Program. B 109 (2–3) (2007) 613–624]. The computed values are strictly better than the Godsil–Newman eigenvalue bounds.

บรรณานุกรม :
Klerk, Etienne de. , Newman, M. W. , Pasechnik, Dmitrii V. , Sotirov, R. . (2551). On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs..
    กรุงเทพมหานคร : Nanyang Technological University, Singapore.
Klerk, Etienne de. , Newman, M. W. , Pasechnik, Dmitrii V. , Sotirov, R. . 2551. "On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs.".
    กรุงเทพมหานคร : Nanyang Technological University, Singapore.
Klerk, Etienne de. , Newman, M. W. , Pasechnik, Dmitrii V. , Sotirov, R. . "On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs.."
    กรุงเทพมหานคร : Nanyang Technological University, Singapore, 2551. Print.
Klerk, Etienne de. , Newman, M. W. , Pasechnik, Dmitrii V. , Sotirov, R. . On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs.. กรุงเทพมหานคร : Nanyang Technological University, Singapore; 2551.