Auswahl der wissenschaftlichen Literatur zum Thema „Subcubic graph“
Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an
Inhaltsverzeichnis
Machen Sie sich mit den Listen der aktuellen Artikel, Bücher, Dissertationen, Berichten und anderer wissenschaftlichen Quellen zum Thema "Subcubic graph" bekannt.
Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.
Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.
Zeitschriftenartikel zum Thema "Subcubic graph"
SKULRATTANAKULCHAI, SAN, und HAROLD N. GABOW. „COLORING ALGORITHMS ON SUBCUBIC GRAPHS“. International Journal of Foundations of Computer Science 15, Nr. 01 (Februar 2004): 21–40. http://dx.doi.org/10.1142/s0129054104002285.
Der volle Inhalt der QuelleHou, Yaoping, und Dijian Wang. „Laplacian integral subcubic signed graphs“. Electronic Journal of Linear Algebra 37 (26.02.2021): 163–76. http://dx.doi.org/10.13001/ela.2021.5699.
Der volle Inhalt der QuelleMa, Hongping, Zhengke Miao, Hong Zhu, Jianhua Zhang und Rong Luo. „Strong List Edge Coloring of Subcubic Graphs“. Mathematical Problems in Engineering 2013 (2013): 1–6. http://dx.doi.org/10.1155/2013/316501.
Der volle Inhalt der QuelleWang, Fang, und Xiaoping Liu. „Coloring 3-power of 3-subdivision of subcubic graph“. Discrete Mathematics, Algorithms and Applications 10, Nr. 03 (Juni 2018): 1850041. http://dx.doi.org/10.1142/s1793830918500416.
Der volle Inhalt der QuelleMOHAR, BOJAN. „Median Eigenvalues of Bipartite Subcubic Graphs“. Combinatorics, Probability and Computing 25, Nr. 5 (21.06.2016): 768–90. http://dx.doi.org/10.1017/s0963548316000201.
Der volle Inhalt der QuelleBu, Yuehua, und Hongguo Zhu. „Strong edge-coloring of subcubic planar graphs“. Discrete Mathematics, Algorithms and Applications 09, Nr. 01 (Februar 2017): 1750013. http://dx.doi.org/10.1142/s1793830917500136.
Der volle Inhalt der QuelleCranston, Daniel W., und Seog-Jin Kim. „List-coloring the square of a subcubic graph“. Journal of Graph Theory 57, Nr. 1 (2007): 65–87. http://dx.doi.org/10.1002/jgt.20273.
Der volle Inhalt der QuelleHE, Zhengyue, Li LIANG und Wei GAO. „Two-distance vertex-distinguishing total coloring of subcubic graphs“. Proceedings of the Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science 24, Nr. 2 (28.06.2023): 113–20. http://dx.doi.org/10.59277/pra-ser.a.24.2.02.
Der volle Inhalt der QuelleWoodall, Douglas R. „The average degree of a subcubic edge‐chromatic critical graph“. Journal of Graph Theory 91, Nr. 2 (29.11.2018): 103–21. http://dx.doi.org/10.1002/jgt.22423.
Der volle Inhalt der QuelleLittle, C. H. C., und F. Rendl. „Operations preserving the pfaffian property of a graph“. Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 50, Nr. 2 (April 1991): 248–57. http://dx.doi.org/10.1017/s1446788700032730.
Der volle Inhalt der QuelleDissertationen zum Thema "Subcubic graph"
Tarhini, Batoul. „Oriented paths in digraphs and the S-packing coloring of subcubic graph“. Electronic Thesis or Diss., Bourgogne Franche-Comté, 2023. http://www.theses.fr/2023UBFCK079.
Der volle Inhalt der QuelleThis PhD thesis is divided into two principal parts: Part I delves into the existenceof oriented paths in digraphs, aiming to establish a connection between a digraph'schromatic number and the existence of specific oriented paths within it as subdigraphs. Digraphs contained in any n-chromatic digraph are called n-universal. We consider two conjectures: Burr's conjecture, which states that every oriented tree of order n is (2n-2)-universal, and El Sahili's conjeture which states that every oriented path of order n is n-universal. For oriented paths in general, the best bound is given by Burr, that is every oriented path of order n is (n − 1)^2-universal. Our objective is to study the existence of an integer k such that any digraph with a chromatic number k, contains a copy of a given oriented path with three blocks as its subdigraph. To achieve our goals, we rely significantly on fundamental concepts, including, induction on the order of a given digraph, final forests, leveling techniques, and strategic digraph decomposition methods. A path P (k1, k2, k3) is an oriented path consisting of k1 forward arcs, followed by k2 backward arcs, and then by k3 forward arcs. For the path P(k,1,l), we have confirmed El Sahili's conjecture in Hamiltonian digraphs. More clearly, we have established the existence of any path P (k, 1, l) of order n in any n-chromatic Hamiltonian digraph. And depending on this result concerning Hamiltonian digraphs, we proved the correctness of El Sahili's conjecture on a more general class of digraphs which is digraphs containing a Hamiltonian directed path. We introduce a new technique which is represented by a decomposition of the digraph into subdigraphs defined by a series of successive operations applied to the digraph relying on the famous theorem of Roy which establishes the existence of a directed path of order n in any n-chromatic digraph. This technique has proven to be instrumental in establishing new linear bounds for the chromatic number of digraphs that lack an oriented path with three blocks. In deed, using this technique, we proved that the path P(k,1,l) satisfies Burr's conjecture.Moreover, for any path with three blocks, P(k,l,r) we establish a linear bound for the chromatic number which improves all the previously reached bounds. In Part II we study the problem of S-packing coloring in graphs. Given a non-decreasing sequence S = (s1, s2, . . . , sk) of positive integers, an S-packing coloring of a graph G is a partition of the vertex set of G into k subsets{V1, V2, . . . , Vk} such that for each 1 ≤ i ≤ k, the distance between any two dis-tinct vertices u and v in Vi is at least si + 1. Our focus is centered on an intriguing conjecture proposed by Brešar et al., which states that packing chromatic number of the subdivision of any subcubic graph is at most 5. Our desired aim is to provide a confirmation of this conjecture for specific classes of subcubic graphs, and to address the unresolved issues raised within this subject matter. An observation for Gastineau and Togni states that if a graph G is (1, 1, 2, 2)-packing colorable, then the chromatic number of its subdivision graph S(G) is at most 5, and hence it satisfies the conjecture. Depending on this observation, and in order to prove the correctness of the conjecture for the class of cubic Halin graphs, we studied its S-packing coloring aiming to prove that it admits a (1, 1, 2, 2)- packing coloring. We proved that a cubic Halin graph is (1, 1, 2, 3)-packing colorable, then it is (1, 1, 2, 2)-packing colorable, and so we confirm the conjecture for this class. Moreover, Gastineau and Togni, after proving that every subcubic graph is (1, 2, 2, 2, 2, 2, 2)-packing colorbale, have posed an open problem on whether every subcubic graph is (1, 2, 2, 2, 2, 2)-packing colorable. We answer this question in affirmative in the particular class we worked on; we proved that cubic Halin graphs are (1, 2, 2, 2, 2, 2)-packing colorable
Lê, Ngoc C. „Algorithms for the Maximum Independent Set Problem“. Doctoral thesis, Technische Universitaet Bergakademie Freiberg Universitaetsbibliothek "Georgius Agricola", 2015. http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-172639.
Der volle Inhalt der QuelleBasavaraju, Manu. „Acyclic Edge Coloring Of Graphs“. Thesis, 2010. http://etd.iisc.ernet.in/handle/2005/2263.
Der volle Inhalt der QuelleBasavaraju, Manu. „Acyclic Edge Coloring Of Graphs“. Thesis, 2010. https://etd.iisc.ac.in/handle/2005/2263.
Der volle Inhalt der QuelleChang, Chia-Jung, und 張家榮. „Triangle-free subcubic graphs with small bipartite density“. Thesis, 2008. http://ndltd.ncl.edu.tw/handle/wgtrc7.
Der volle Inhalt der Quelle國立中山大學
應用數學系研究所
96
Suppose G is a graph with n vertices and m edges. Let n′ be the maximum number of vertices in an induced bipartite subgraph of G and let m′ be the maximum number of edges in a spanning bipartite subgraph of G. Then b(G) = m′/m is called the bipartite density of G, and b∗(G) = n′/n is called the bipartite ratio of G. It is proved in [18] that if G is a 2-connected triangle-free subcubic graph, then apart from seven exceptional graphs, we have b(G) ≥ 17/21. If G is a 2-connected triangle-free subcubic graph, then b∗(G) ≥ 5/7 provided that G is not the Petersen graph and not the dodecahedron. These two results are consequences of a more technical result which is proved by induction: If G is a 2-connected triangle-free subcubic graph with minimum degree 2, then G has an induced bipartite subgraph H with |V (H)| ≥ (5n3 + 6n2 + ǫ(G))/7, where ni = ni(G) are the number of degree i vertices of G, and ǫ(G) ∈ {−2,−1, 0, 1}. To determine ǫ(G), four classes of graphs G1, G2, G3 and F-cycles are onstructed. For G ∈ Gi, we have ǫ(G) = −3 + i and for an F-cycle G, we have ǫ(G) = 0. Otherwise, ǫ(G) = 1. To construct these graph classes, eleven graph operations are used. This thesis studies the structural property of graphs in G1, G2, G3. First of all, a computer algorithm is used to generate all the graphs in Gi for i = 1, 2, 3. Let P be the set of 2-edge connected subcubic triangle-free planar graphs with minimum degree 2. Let G′ 1 be the set of graphs in P with all faces of degree 5, G′2 the set of graphs in P with all faces of degree 5 except that one face has degree 7, and G′3 the set of graphs in P with all faces of degree 5 except that either two faces are of degree 7 or one face is of degree 9. By checking the graphs generated by the computer algorithm, it is easy to see that Gi ⊆ G′i for i = 1, 2, 3. The main results of this thesis are that for i = 1, 2, Gi = G′i and G′3 = G3 ∪R, where R is a set of nine F-cycles.
Wang, Wei Lin, und 王維琳. „On Complexity of Total Vertex Cover on Subcubic Graphs“. Thesis, 2016. http://ndltd.ncl.edu.tw/handle/21471822635515100142.
Der volle Inhalt der Quelle國立清華大學
資訊系統與應用研究所
104
A total vertex cover is a vertex cover whose induced subgraph consists of a set of connected components, each of which contains at least two vertices. A t-total vertex cover is a total vertex cover where each component of its induced subgraph contains at least t vertices. The total vertex cover (TVC) problem and the t-total vertex cover (t-TVC) problem ask for the corresponding cover set with minimum cardinality, respectively. In this paper, we first show that the t-TVC problem is NP-complete for connected subcubic grid graphs of arbitrary large girth. Next, we show that the t-TVC problem is NP-complete for 3-connected cubic planar graphs. Moreover, we show that the t-TVC problem is APX-complete for connected subcubic graphs of arbitrary large girth.
Lê, Ngoc C. „Algorithms for the Maximum Independent Set Problem“. Doctoral thesis, 2014. https://tubaf.qucosa.de/id/qucosa%3A22990.
Der volle Inhalt der QuelleBuchteile zum Thema "Subcubic graph"
Eppstein, David. „Planar Lombardi Drawings for Subcubic Graphs“. In Graph Drawing, 126–37. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-36763-2_12.
Der volle Inhalt der QuelleHarutyunyan, Ararat, Michael Lampis, Vadim Lozin und Jérôme Monnot. „Maximum Independent Sets in Subcubic Graphs: New Results“. In Graph-Theoretic Concepts in Computer Science, 40–52. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-30786-8_4.
Der volle Inhalt der QuelleGiannopoulou, Archontia C., O.-joung Kwon, Jean-Florent Raymond und Dimitrios M. Thilikos. „Packing and Covering Immersion Models of Planar Subcubic Graphs“. In Graph-Theoretic Concepts in Computer Science, 74–84. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016. http://dx.doi.org/10.1007/978-3-662-53536-3_7.
Der volle Inhalt der QuelleCheng, Christine, Eric McDermid und Ichiro Suzuki. „Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs“. In Graph-Theoretic Concepts in Computer Science, 107–18. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-25870-1_11.
Der volle Inhalt der QuelleGiannopoulou, Archontia C., O.-joung Kwon, Jean-Florent Raymond und Dimitrios M. Thilikos. „Erratum to: Packing and Covering Immersion Models of Planar Subcubic Graphs“. In Graph-Theoretic Concepts in Computer Science, E1. Berlin, Heidelberg: Springer Berlin Heidelberg, 2017. http://dx.doi.org/10.1007/978-3-662-53536-3_26.
Der volle Inhalt der QuelleDvořák, Zdeněk, Jean-Sébastien Sereni und Jan Volec. „Subcubic triangle-free graphs have fractional chromatic number at most 14/5“. In The Seventh European Conference on Combinatorics, Graph Theory and Applications, 497–502. Pisa: Scuola Normale Superiore, 2013. http://dx.doi.org/10.1007/978-88-7642-475-5_79.
Der volle Inhalt der QuelleGabow, Harold N., und San Skulrattanakulchai. „Coloring Algorithms on Subcubic Graphs“. In Lecture Notes in Computer Science, 67–76. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-45655-4_9.
Der volle Inhalt der QuelleBoyd, Sylvia, René Sitters, Suzanne van der Ster und Leen Stougie. „TSP on Cubic and Subcubic Graphs“. In Integer Programming and Combinatoral Optimization, 65–77. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-20807-2_6.
Der volle Inhalt der QuelleKang, Ross J., Matthias Mnich und Tobias Müller. „Induced Matchings in Subcubic Planar Graphs“. In Algorithms – ESA 2010, 112–22. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-15781-3_10.
Der volle Inhalt der QuelleGómez, Renzo, Flávio Miyazawa und Yoshiko Wakabayashi. „Minimum t-Spanners on Subcubic Graphs“. In WALCOM: Algorithms and Computation, 365–80. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-96731-4_30.
Der volle Inhalt der QuelleKonferenzberichte zum Thema "Subcubic graph"
Faria, Luerbio, Mauro Nigro und Diana Sasaki. „On the conformable colorings of k-regular graphs“. In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2023. http://dx.doi.org/10.5753/etc.2023.230063.
Der volle Inhalt der QuelleLintzmayer, Carla N., Guilherme O. Mota, Lucas S. da Rocha und Maycon Sambinelli. „Some results on irregular decomposition of graphs“. In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2023. http://dx.doi.org/10.5753/etc.2023.230304.
Der volle Inhalt der QuelleAbboud, Amir, Fabrizio Grandoni und Virginia Vassilevska Williams. „Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter“. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014. http://dx.doi.org/10.1137/1.9781611973730.112.
Der volle Inhalt der QuelleWeffort-Santos, Celso A., Christiane N. Campos und Rafael C. S. Schouery. „Proper gap-labellings: on the edge and vertex variants“. In XXXII Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/ctd.2019.6343.
Der volle Inhalt der QuelleTang, Chang, Xinwang Liu, En Zhu, Lizhe Wang und Albert Zomaya. „Hyperspectral Band Selection via Spatial-Spectral Weighted Region-wise Multiple Graph Fusion-Based Spectral Clustering“. In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/418.
Der volle Inhalt der QuelleAbboud, Amir, Robert Krauthgamer und Ohad Trabelsi. „Subcubic algorithms for Gomory–Hu tree in unweighted graphs“. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: ACM, 2021. http://dx.doi.org/10.1145/3406325.3451073.
Der volle Inhalt der QuelleKuzmin, Nikita Alexandrovich, und Dmitry Sergeevich Malyshev. „On connected subcubic graphs with n vertices and n+3 edges having maximum number of matchings“. In Academician O.B. Lupanov 14th International Scientific Seminar "Discrete Mathematics and Its Applications". Keldysh Institute of Applied Mathematics, 2022. http://dx.doi.org/10.20948/dms-2022-58.
Der volle Inhalt der Quelle