Graphs with cyclomatic number three having panconnected square
| Autor: | Wanida Hemakul, Sirirat Singhun, Gek L. Chia |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
010102 general mathematics Circuit rank Cyclomatic complexity 0102 computer and information sciences 01 natural sciences Hamiltonian path Graph Combinatorics symbols.namesake 010201 computation theory & mathematics symbols Discrete Mathematics and Combinatorics 0101 mathematics Mathematics |
| Zdroj: | Discrete Mathematics, Algorithms and Applications. :1750067 |
| ISSN: | 1793-8317 1793-8309 |
| Popis: | The square of a graph [Formula: see text] is the graph obtained from [Formula: see text] by adding edges joining those pairs of vertices whose distance from each other in [Formula: see text] is two. If [Formula: see text] is connected, then the cyclomatic number of [Formula: see text] is defined as [Formula: see text]. Graphs with cyclomatic number not more than [Formula: see text] whose square are panconnected have been characterized, among other things, in [G. L. Chia, S. H. Ong and L. Y. Tan, On graphs whose square have strong Hamiltonian properties, Discrete Math. 309 (2009) 4608–4613, G. L. Chia, W. Hemakul and S. Singhun, Graphs with cyclomatic number two having panconnected square, Discrete Math. 311 (2011) 850–855]. Here, we show that if [Formula: see text] has cyclomatic number [Formula: see text] and [Formula: see text] is panconnected, then [Formula: see text] is one of the eight families of graphs, [Formula: see text], defined in the paper. Further, we obtain necessary and sufficient conditions for three larger families of graphs (which contains [Formula: see text] as special cases) whose square are panconnected. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|