Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers

DOI10.1016/S0166-218X(02)00597-8zbMath1025.05059OpenAlexW1991643774MaRDI QIDQ1406039

Aleksander Vesel, Sandi Klavžar

Publication date: 9 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00597-8

zbMATH Keywords

independence numberCartesian product of graphsrotagraphstrong product of graphsdynamic algorithm\((2,1)\)-coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (22)

A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs ⋮ The minimum span of \(L(2,1)\)-labelings of certain generalized Petersen graphs ⋮ \(L(3,2,1)\)-labeling of triangular and toroidal grids ⋮ \(L(j, k)\)-number of direct product of path and cycle ⋮ Labeling crossed prisms with a condition at distance two ⋮ On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs ⋮ Distance-two labelings of digraphs ⋮ \(L(2, 1)\)-labeling of the Cartesian and strong product of two directed cycles ⋮ Exact \(\lambda\)-numbers of generalized Petersen graphs of certain higher-orders and on Möbius strips ⋮ \((d, n)\)-packing colorings of infinite lattices ⋮ On the \(L(2,1)\)-labelings of amalgamations of graphs ⋮ Generic algorithms for some decision problems on fasciagraphs and rotagraphs ⋮ The minimum span of \(L(2,1)\)-labelings of generalized flowers ⋮ \(L (j, k)\)- and circular \(L(j, k)\)-labellings for the products of complete graphs ⋮ \(L(2,1)\)-labeling of direct product of paths and cycles ⋮ \(L(2,1)\)-labelings of Cartesian products of two cycles ⋮ A survey on labeling graphs with a condition at distance two ⋮ The \(k\)-distance independence number and 2-distance chromatic number of Cartesian products of cycles ⋮ \(L(2,1)\)-labeling for brick product graphs ⋮ On \(L(d,1)\)-labeling of Cartesian product of a cycle and a path ⋮ \(L(2,1)\)-labeling of strong products of cycles ⋮ Optimal \(L(d,1)\)-labelings of certain direct products of cycles and Cartesian products of cycles

Uses Software

• NISPOC

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The matching polynomial of a polygraph
• The independence number of the strong product of cycles
• Geometric algorithms and combinatorial optimization
• Relating path coverings to vertex labellings with a condition at distance two
• Distance-related invariants on polygraphs
• Improved lower bound on the Shannon capacity of \(C_7\)
• Algebraic approach to fasciagraphs and rotagraphs
• A note on the chromatic number of the square of the Cartesian product of two cycles
• Numerical invariants and the strong product of graphs
• Labeling Products of Complete Graphs with a Condition at Distance Two
• Optimal L(2,1)-labeling of Cartesian products of cycles, with an application to independent domination
• Labelling Graphs with a Condition at Distance 2
• Graph labeling and radio channel assignment
• Labeling Chordal Graphs: Distance Two Condition
• Optimal L(2, 1)-labeling of strong products of cycles [transmitter frequency assignment]
• On the $\lambda$-Number of $Q_n $ and Related Graphs
• The $L(2,1)$-Labeling Problem on Graphs
• Independence numbers of product graphs

This page was built for publication: Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers