Добірка наукової літератури з теми "Subcubic graph"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Subcubic graph".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Subcubic graph":
SKULRATTANAKULCHAI, SAN, and HAROLD N. GABOW. "COLORING ALGORITHMS ON SUBCUBIC GRAPHS." International Journal of Foundations of Computer Science 15, no. 01 (February 2004): 21–40. http://dx.doi.org/10.1142/s0129054104002285.
Hou, Yaoping, and Dijian Wang. "Laplacian integral subcubic signed graphs." Electronic Journal of Linear Algebra 37 (February 26, 2021): 163–76. http://dx.doi.org/10.13001/ela.2021.5699.
Ma, Hongping, Zhengke Miao, Hong Zhu, Jianhua Zhang, and 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.
Wang, Fang, and Xiaoping Liu. "Coloring 3-power of 3-subdivision of subcubic graph." Discrete Mathematics, Algorithms and Applications 10, no. 03 (June 2018): 1850041. http://dx.doi.org/10.1142/s1793830918500416.
MOHAR, BOJAN. "Median Eigenvalues of Bipartite Subcubic Graphs." Combinatorics, Probability and Computing 25, no. 5 (June 21, 2016): 768–90. http://dx.doi.org/10.1017/s0963548316000201.
Bu, Yuehua, and Hongguo Zhu. "Strong edge-coloring of subcubic planar graphs." Discrete Mathematics, Algorithms and Applications 09, no. 01 (February 2017): 1750013. http://dx.doi.org/10.1142/s1793830917500136.
Cranston, Daniel W., and Seog-Jin Kim. "List-coloring the square of a subcubic graph." Journal of Graph Theory 57, no. 1 (2007): 65–87. http://dx.doi.org/10.1002/jgt.20273.
HE, Zhengyue, Li LIANG, and 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, no. 2 (June 28, 2023): 113–20. http://dx.doi.org/10.59277/pra-ser.a.24.2.02.
Woodall, Douglas R. "The average degree of a subcubic edge‐chromatic critical graph." Journal of Graph Theory 91, no. 2 (November 29, 2018): 103–21. http://dx.doi.org/10.1002/jgt.22423.
Little, C. H. C., and F. Rendl. "Operations preserving the pfaffian property of a graph." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 50, no. 2 (April 1991): 248–57. http://dx.doi.org/10.1017/s1446788700032730.
Дисертації з теми "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.
This 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.
Basavaraju, Manu. "Acyclic Edge Coloring Of Graphs." Thesis, 2010. http://etd.iisc.ernet.in/handle/2005/2263.
Basavaraju, Manu. "Acyclic Edge Coloring Of Graphs." Thesis, 2010. https://etd.iisc.ac.in/handle/2005/2263.
Chang, Chia-Jung, and 張家榮. "Triangle-free subcubic graphs with small bipartite density." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/wgtrc7.
國立中山大學
應用數學系研究所
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, and 王維琳. "On Complexity of Total Vertex Cover on Subcubic Graphs." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/21471822635515100142.
國立清華大學
資訊系統與應用研究所
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.
Частини книг з теми "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.
Harutyunyan, Ararat, Michael Lampis, Vadim Lozin, and 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.
Giannopoulou, Archontia C., O.-joung Kwon, Jean-Florent Raymond, and 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.
Cheng, Christine, Eric McDermid, and 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.
Giannopoulou, Archontia C., O.-joung Kwon, Jean-Florent Raymond, and 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.
Dvořák, Zdeněk, Jean-Sébastien Sereni, and 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.
Gabow, Harold N., and 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.
Boyd, Sylvia, René Sitters, Suzanne van der Ster, and 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.
Kang, Ross J., Matthias Mnich, and 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.
Gómez, Renzo, Flávio Miyazawa, and 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.
Тези доповідей конференцій з теми "Subcubic graph":
Faria, Luerbio, Mauro Nigro, and 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.
Lintzmayer, Carla N., Guilherme O. Mota, Lucas S. da Rocha, and 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.
Abboud, Amir, Fabrizio Grandoni, and 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.
Weffort-Santos, Celso A., Christiane N. Campos, and 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.
Tang, Chang, Xinwang Liu, En Zhu, Lizhe Wang, and 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.
Abboud, Amir, Robert Krauthgamer, and 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.
Kuzmin, Nikita Alexandrovich, and 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.