×

Finding the edge ranking number through vertex partitions. (English) Zbl 1263.05032

Summary: An edge coloring \(c^{\prime}:E\to \{1,2,\dots ,t\}\) of a graph \(G\)=(\(V,E\)) is an edge \(t\)-ranking if for any two edges of the same color, every path between them contains an intermediate edge with a larger color. The edge ranking number \(\chi_{r}^{\prime}(G)\) is the smallest value of \(t\) such that \(G\) has an edge \(t\)-ranking.
In this paper, we introduce a relation between edge ranking number and vertex partitions. By using the proposed recurrence formula, we show that the edge ranking number of the Sierpiński graph \(\chi_{r}^{\prime}(S(n,k))=n\chi_{r}^{\prime}(K_{k})\) for any \(n,k\geq 2\) where \(K_{k}\) denotes a complete graph of \(k\) vertices.

MSC:

05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aspvall, B.; Heggernes, P., Finding minimum height elimination trees for interval graphs in polynomial time, BIT Numerical Mathematics, 34, 484-509 (1994) · Zbl 0822.68071
[2] Bodlaender, H.; Deogun, J.; Jansen, K.; Kloks, T.; Kratsch, D.; Müller, H.; Tuza, Z., Rankings of graphs, SIAM Journal on Discrete Mathematics, 11, 168-181 (1998) · Zbl 0907.68137
[3] Bodlaender, H.; Gilbert, J.; Hafsteinsson, H.; Kloks, T., Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, Journal of Algorithms, 18, 238-255 (1995) · Zbl 0818.68118
[5] de la Torre, P.; Greenlaw, R.; Schäffer, A. A., Optimal edge ranking of trees in polynomial time, Algorithmica, 13, 592-618 (2005) · Zbl 0826.68093
[6] Deogun, J.; Kloks, T.; Kratsch, D.; Müller, H., On the vertex ranking problem for trapezoid, circular-arc and other graphs, Discrete Applied Mathematics, 98, 39-63 (1999) · Zbl 0937.68093
[7] Dereniowski, D., Edge ranking of weighted trees, Discrete Applied Mathematics, 154, 1198-1209 (2006) · Zbl 1095.68079
[8] Diestel, R., Graph Theory (2000), Springer-Verlag · Zbl 0945.05002
[9] Duff, S.; Reid, J., The multifrontal solution of indefinite sparse symmetric linear equations, ACM Transactions on Mathematical Software, 9, 302-325 (1983) · Zbl 0515.65022
[10] Gravier, S.; Klavžar, S.; Mollard, M., Codes and \(L(2, 1)\)-labelings in Sierpiński graphs, Taiwanese Journal of Mathematics, 9, 671-681 (2005) · Zbl 1093.05059
[11] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading · Zbl 0182.57702
[12] Hinz, A.; Parisse, D., Coloring Hanoi and Sierpiński graphs, Discrete Mathematics, 312, 1521-1535 (2012) · Zbl 1239.05066
[13] Hinz, A., Pascal’s triangle and the Tower of Hanoi, American Mathematical Monthly, 99, 538-544 (1992) · Zbl 0782.05003
[14] Hinz, A.; Klavžar, S.; Milutinović, U.; Parisse, D.; Petr, C., Metric properties of the Tower of Hanoi graphs and Stern’s diatomic sequence, European Journal of Combinatorics, 26, 693-708 (2005) · Zbl 1060.05007
[15] Iyer, A.; Ratliff, H.; Vijayan, G., Optimal node ranking of trees, Information Processing Letters, 28, 225-229 (1988) · Zbl 0661.68063
[16] Iyer, A.; Ratliff, H.; Vijayan, G., On an edge ranking problem of trees and graphs, Discrete Applied Mathematics, 30, 43-52 (1991) · Zbl 0727.05053
[17] Jakovac, M.; Klavžar, S., Vertex-, edge-, and total-colorings of Sierpiński-like graphs, Discrete Mathematics, 309, 1548-1556 (2009) · Zbl 1198.05056
[18] Kashema, A.; Zhou, X.; Nishizekia, T., Algorithms for generalized vertex-rankings of partial \(k\)-trees, Theoretical Computer Science, 240, 407-427 (2000) · Zbl 0945.68142
[19] Katchalski, M.; McCuaig, W.; Seager, S., Ordered colourings, Discrete Mathematics, 142, 141-154 (1995) · Zbl 0842.05032
[20] Klavžar, S.; Milutinović, U., Graphs \(S(n, k)\) and a variant of the Tower of Hanoi problem, Czechoslovak Mathematical Journal, 47, 95-104 (1997) · Zbl 0898.05042
[21] Lam, T.; Yue, F., Edge ranking of graphs is hard, Discrete Applied Mathematics, 85, 71-86 (1998) · Zbl 0902.68088
[22] Lam, T.; Yue, F., Optimal edge ranking of trees in linear time, Algorithmica, 30, 12-33 (2001) · Zbl 0984.68200
[23] Leiserson, C., Area-efficient graph layouts (for VLSI), (Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science (1980), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA), 270-281
[24] Liu, J., The role of elimination trees in sparse factorization, SIAM Journal on Matrix Analysis and Applications, 11, 134-172 (1990) · Zbl 0697.65013
[25] Nakayama, S.; Masuyama, S., A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs, Information Processing Letters, 103, 216-221 (2007) · Zbl 1185.05122
[26] Schäffer, A., Optimal node ranking of trees in linear time, Information Processing Letters, 33, 91-96 (1989) · Zbl 0683.68038
[27] Sen, A.; Deng, H.; Guha, S., On a graph partition problem with application to VLSI layout, Information Processing Letters, 43, 87-94 (1992) · Zbl 0764.68132
[28] Zhou, X.; Kashem, M.; Nishizeki, T., Generalized edge-rankings of trees, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 81-A, 2, 310-320 (1998) · Zbl 0945.68142
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.