WEKO3
アイテム
{"_buckets": {"deposit": "8405f0b3-c50b-4b01-a13c-427b2ad4678a"}, "_deposit": {"created_by": 3, "id": "1138", "owners": [3], "pid": {"revision_id": 0, "type": "depid", "value": "1138"}, "status": "published"}, "_oai": {"id": "oai:uec.repo.nii.ac.jp:00001138", "sets": ["14"]}, "author_link": ["7102"], "control_number": "1138", "item_10006_alternative_title_1": {"attribute_name": "その他(別言語等)のタイトル", "attribute_value_mlt": [{"subitem_alternative_title": "グラフの因子に関する研究", "subitem_alternative_title_language": "ja"}]}, "item_10006_date_granted_11": {"attribute_name": "学位授与年月日", "attribute_value_mlt": [{"subitem_dategranted": "2009-03-24"}]}, "item_10006_degree_grantor_9": {"attribute_name": "学位授与機関", "attribute_value_mlt": [{"subitem_degreegrantor": [{"subitem_degreegrantor_name": "電気通信大学"}]}]}, "item_10006_degree_name_8": {"attribute_name": "学位名", "attribute_value_mlt": [{"subitem_degreename": "博士(理学)"}]}, "item_10006_description_10": {"attribute_name": "学位授与年度", "attribute_value_mlt": [{"subitem_description": "2008", "subitem_description_type": "Other"}]}, "item_10006_description_7": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "In this thesis, we deal with a problem of factors in graphs.First, we consider a relationship between an f-factor of a graph and an f-factorof some subgraphs of the graph. Let G be a graph. Katerinis [Some results onthe existence of 2n-factors in terms of vertex-deleted subgraphs, Ars Combin. 16]proved that for an even integer k, if G - x has a k-factor for each x ∈ V (G), thenG has a k-factor. Enomoto and Tokuda [Complete-factors and f-factors, DiscreteMath. 220] generalized Katerinis’s result to f-factors, and proved that if F is acomplete-factor of G with ω(F) 2, and G-C has an f-factor for each componentC of F, then G has an f-factor. Immediately, we have the following corollary fromEnomoto and Tokuda’s theorem by setting F=|V (G)|K1. The corollary is that ifG - x has an f-factor for each x ∈ V (G), then G has an f-factor. In Katerinis’sresult and the corollary, every vertex x is examined to satisfy the condition thatG-x has an f-factor. Then a question arises whether all the vertices are necessarilyexamined. Motivated by the above question, we consider the same type of theorems,but with some “unexamined vertices.” We show the following our theorems. LetG be a graph, and let X be a subset of V (G) with |V (G) - X| 2, and let fbe a non-negative integer-valued function defined on V (G) withΣx∈V (G) f(x) even.We prove that ifΣx∈X degG(x) 2|V (G) - X| - 1 and if G - x has an f-factorfor each x ∈ V (G) - X, then G has an f-factor. Moreover, if G excludes anisolated vertex, then we can replace the conditionΣx∈X degG(x) 2|V (G)-X|-1withΣx∈X degG(x) 2|V (G) - X| + |X| - 3. Furthermore the condition will be Σx∈X deg(x) 2|V (G) -X| - 1 when |X| = 1. On the other hand, we also extendEnomoto and Tokuda’s result, and show that it suffices to consider a complete-factorof G - X instead of G for some specified X ⊂ V (G). Let F be a complete-factorof G - X with ω(F) 2. If G - C has an f-factor for each component C of F,then G has an f-factor in one of the following cases: (1)Σx∈X degG(x) ω(F)-1;(2) ω(F) is even andΣx∈X degG(x) ω(F) + 1; (3) G has no isolated vertices andΣx∈X degG(x) ω(F)+|X|-2; or (4) G has no isolated vertices, ω(F) is even andΣx∈X degG(x) ω(F) + |X| - 1. We show that the results in this thesis are sharpin some sense.Second, we consider a k-factor with prescribed and proscribed edges in regulargraphs. Let , m, n, r be integers such that 2 r, and r 4, and m, n 0.Suppose G is an r-regular -edge-connected graph and that k is an even integerwith m k r2 . We say that G is an (m, n; k)-factor graph if for each disjoint pairE1,E2 ⊂ E(G) with |E1| = m and |E2| = n, G has a k-factor F such that E1 ⊂ E(F)and E2 ∩ E(F) = . In this thesis we consider when G is an (m, n; k)-factor graphand characterize those graphs that fail for certain parameters , m, n, r, k.", "subitem_description_type": "Abstract"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "木村, 健司", "creatorNameLang": "ja"}, {"creatorName": "キムラ, ケンジ", "creatorNameLang": "ja-Kana"}, {"creatorName": "Kimura, Kenji", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "7102", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2016-09-16"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "9000000338.pdf", "filesize": [{"value": "352.8 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 352800.0, "url": {"label": "9000000338.pdf", "url": "https://uec.repo.nii.ac.jp/record/1138/files/9000000338.pdf"}, "version_id": "321b5b2d-a823-412f-adfa-6f8c2be3294c"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "thesis", "resourceuri": "http://purl.org/coar/resource_type/c_46ec"}]}, "item_title": "STUDIES ON FACTORS OF GRAPHS", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "STUDIES ON FACTORS OF GRAPHS", "subitem_title_language": "en"}]}, "item_type_id": "10006", "owner": "3", "path": ["14"], "permalink_uri": "https://uec.repo.nii.ac.jp/records/1138", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2009-03-24"}, "publish_date": "2009-03-24", "publish_status": "0", "recid": "1138", "relation": {}, "relation_version_is_last": true, "title": ["STUDIES ON FACTORS OF GRAPHS"], "weko_shared_id": -1}
STUDIES ON FACTORS OF GRAPHS
https://uec.repo.nii.ac.jp/records/1138
https://uec.repo.nii.ac.jp/records/1138bf21ef95-b921-4410-ac2d-22fbaf8f1274
名前 / ファイル | ライセンス | アクション |
---|---|---|
9000000338.pdf (352.8 kB)
|
|
Item type | 学位論文 / Thesis or Dissertation(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2009-03-24 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | STUDIES ON FACTORS OF GRAPHS | |||||
言語 | ||||||
言語 | eng | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||
資源タイプ | thesis | |||||
その他(別言語等)のタイトル | ||||||
その他のタイトル | グラフの因子に関する研究 | |||||
言語 | ja | |||||
著者 |
木村, 健司
× 木村, 健司 |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | In this thesis, we deal with a problem of factors in graphs.First, we consider a relationship between an f-factor of a graph and an f-factorof some subgraphs of the graph. Let G be a graph. Katerinis [Some results onthe existence of 2n-factors in terms of vertex-deleted subgraphs, Ars Combin. 16]proved that for an even integer k, if G - x has a k-factor for each x ∈ V (G), thenG has a k-factor. Enomoto and Tokuda [Complete-factors and f-factors, DiscreteMath. 220] generalized Katerinis’s result to f-factors, and proved that if F is acomplete-factor of G with ω(F) 2, and G-C has an f-factor for each componentC of F, then G has an f-factor. Immediately, we have the following corollary fromEnomoto and Tokuda’s theorem by setting F=|V (G)|K1. The corollary is that ifG - x has an f-factor for each x ∈ V (G), then G has an f-factor. In Katerinis’sresult and the corollary, every vertex x is examined to satisfy the condition thatG-x has an f-factor. Then a question arises whether all the vertices are necessarilyexamined. Motivated by the above question, we consider the same type of theorems,but with some “unexamined vertices.” We show the following our theorems. LetG be a graph, and let X be a subset of V (G) with |V (G) - X| 2, and let fbe a non-negative integer-valued function defined on V (G) withΣx∈V (G) f(x) even.We prove that ifΣx∈X degG(x) 2|V (G) - X| - 1 and if G - x has an f-factorfor each x ∈ V (G) - X, then G has an f-factor. Moreover, if G excludes anisolated vertex, then we can replace the conditionΣx∈X degG(x) 2|V (G)-X|-1withΣx∈X degG(x) 2|V (G) - X| + |X| - 3. Furthermore the condition will be Σx∈X deg(x) 2|V (G) -X| - 1 when |X| = 1. On the other hand, we also extendEnomoto and Tokuda’s result, and show that it suffices to consider a complete-factorof G - X instead of G for some specified X ⊂ V (G). Let F be a complete-factorof G - X with ω(F) 2. If G - C has an f-factor for each component C of F,then G has an f-factor in one of the following cases: (1)Σx∈X degG(x) ω(F)-1;(2) ω(F) is even andΣx∈X degG(x) ω(F) + 1; (3) G has no isolated vertices andΣx∈X degG(x) ω(F)+|X|-2; or (4) G has no isolated vertices, ω(F) is even andΣx∈X degG(x) ω(F) + |X| - 1. We show that the results in this thesis are sharpin some sense.Second, we consider a k-factor with prescribed and proscribed edges in regulargraphs. Let , m, n, r be integers such that 2 r, and r 4, and m, n 0.Suppose G is an r-regular -edge-connected graph and that k is an even integerwith m k r2 . We say that G is an (m, n; k)-factor graph if for each disjoint pairE1,E2 ⊂ E(G) with |E1| = m and |E2| = n, G has a k-factor F such that E1 ⊂ E(F)and E2 ∩ E(F) = . In this thesis we consider when G is an (m, n; k)-factor graphand characterize those graphs that fail for certain parameters , m, n, r, k. | |||||
学位名 | ||||||
学位名 | 博士(理学) | |||||
学位授与機関 | ||||||
学位授与機関名 | 電気通信大学 | |||||
学位授与年度 | ||||||
内容記述タイプ | Other | |||||
内容記述 | 2008 | |||||
学位授与年月日 | ||||||
学位授与年月日 | 2009-03-24 |