Structural properties of subdivided-line graphs

DOI10.1016/j.jda.2015.01.008zbMath1325.05139OpenAlexW2044393195MaRDI QIDQ2018541

Toru Hasunuma

Publication date: 24 March 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2015.01.008

zbMATH Keywords

book embeddingindependent spanning treesconnected dominating setedge-disjoint Hamilton cyclescompletely independent spanning treesSierpiński graphhub setHamiltonian-connectivitysubdivided line graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

Related Items

On the number of spanning trees, the Laplacian eigenvalues, and the Laplacian Estrada index of subdivided-line graphs ⋮ Integrity of total transformation graphs ⋮ Average trapping time on a type of horizontally segmented three dimensional Sierpinski gasket network with two types of locally self-similar structures ⋮ Constructions of universalized Sierpiński graphs based on labeling manipulations ⋮ Completely independent spanning trees in line graphs ⋮ COHERENCE ANALYSIS FOR ITERATED LINE GRAPHS OF MULTI-SUBDIVISION GRAPH ⋮ A survey and classification of Sierpiński-type graphs ⋮ Graphs that are simultaneously efficient open domination and efficient closed domination graphs ⋮ Maximum matchings in scale-free networks with identical degree distribution ⋮ A parallel algorithm to construct edge independent spanning trees on the line graphs of conditional bijective connection networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Disjoint Hamiltonian cycles in recursive circulant graphs
• Independent spanning trees of chordal rings
• Sierpiński graphs as spanning subgraphs of Hanoi graphs
• Global strong defensive alliances of Sierpiński-like graphs
• Two counterexamples on completely independent spanning trees
• Coloring Hanoi and Sierpiński graphs
• The hamiltonicity and path \(t\)-coloring of Sierpiński-like graphs
• The hub number of Sierpiński-like graphs
• The pagenumber of the class of bandwidth-k graphs is \(k-1\)
• Edge-disjoint Hamilton cycles in graphs
• Shortest paths in Sierpiński graphs
• The hub number of a graph
• Disjoint Hamilton cycles in the star graph
• On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\)
• Vertex-, edge-, and total-colorings of Sierpiński-like graphs
• Improved book-embeddings of incomplete hypercubes
• Hamiltonian connectivity of the WK-recursive network with faulty nodes
• Optimal book embeddings of the FFT, Benes, and barrel shifter networks
• The multi-tree approach to reliability in distributed networks
• Embedding planar graphs in four pages
• The book thickness of a graph
• Independent trees in planar graphs
• Embedding de Bruijn, Kautz and shuffle-exchange networks in books
• The average eccentricity of Sierpiński graphs
• The linear \(t\)-colorings of Sierpiński-like graphs
• New results on variants of covering codes in Sierpiński graphs
• The connected hub number and the connected domination number
• Line Digraph Iterations and the (d, k) Digraph Problem
• Three tree-paths
• Pagenumber of complete bipartite graphs
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Graphs S(n, k) and a Variant of the Tower of Hanoi Problem
• Genus g Graphs Have Pagenumber O(√g)
• Completely independent spanning trees in torus networks
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding iterated line digraphs in books
• On distances in Sierpiński graphs: Almost-extreme vertices and metric dimension
• Independent Spanning Trees on Multidimensional Torus Networks
• Finding Four Independent Trees
• Crossing numbers of Sierpiński‐like graphs
• The pagenumber of \(k\)-trees is \(O(k)\)
• Completely independent spanning trees in the underlying graph of a line digraph
• Independent spanning trees with small depths in iterated line digraphs

This page was built for publication: Structural properties of subdivided-line graphs