Cycle Discrepancy of d-Colorable Graphs

Article Sidebar

PDF
Published: Jun 22, 2016

Main Article Content

Laeeq Aslam
Shahzad Sarwar
Muhammad Murtaza Yousaf
Waqar ul Qounain

Abstract

We show that cycle discrepancy of a 3-colorable graph, G, on at least five vertices is bounded by 2 n 3 2 ; that is, cycdisc(G)  2n 3 2 . We also show that this bound is best possible by constructing 3-colorable graphs, on at least five vertices for which cycle discrepancy is at least 2n 3 2 . Let Gt be the set of 3-colorable graphs on n ≥ 5 vertices with t vertices in the smallest color class. We show that for a graph, G from Gt , cycdisc(G)  2 t 2 . Furthermore a graph G' exists in Gt with large cycle discrepancy, such that cycdisc (G')  2 t 2 for t ≥ 1. We also construct such d-colorable graphs for d> 3 that have maximum possible cycle discrepancy.

Article Details

Issue
2016: Volume 18 JAN 2016
Section
Electrical Engineering and Computer Science

References

JICA report (2000), Feasibility study on the development of Munda dam multipurpose project in Islamic Republic of Pakistan.

Singh, P., Jain, S. K., & Kumar, N. (1997). Estimation of snow and glacier-melt contribution to the Chenab River, Western Himalaya. Mountain Research and Development, 49-56.

Chyurlia, J. P. (1983) Water Resources Report, Nepal Land Resources Mapping Project. Renting Earth Sciences Limited, Ottawa

Lim, K. J., Engel, B. A., Tang, Z., Choi, J., Kim, K. S., Muthukrishnan, S., & Tripathy, D. (2005). Automated web gis based hydrograph analysis tool, WHAT1.

Arnold, J. G., & Allen, P. M. (1999). Automated methods for estimating base flow and ground water recharge from stream flow records .

Michel, C., Andréassian, V., & Perrin, C. (2005). Soil Conservation Service Curve Number method: How to mend a wrong soil moisture accounting procedure?. Water Resources Research, 41(2).

Soulis, K. X., Valiantzas, J. D., Dercas, N., & Londra, P. A. (2009). Analysis of the runoff generation mechanism for the investigation of the SCS-CN method applicability to a partial area experimental watershed. Hydrol Earth Syst Sci, 6, 373-400.

Queensland Urban Drainage Manual – Volume 1 second edition 2007, http://www.dews.qld.gov.au/__data/assets/pdf_f ile/0008/78128/qudm2013-provisional.pdf

Rutledge, C. W., & Whitaker Jr, N. A. (2003). U.S. Patent No. 6,650,998. Washington, DC: U.S. Patent and Trademark Office.

Tallaksen, L. M. (1995). A review of baseflow recession analysis. Journal of hydrology, 165(1), 349-370.

Sharma, K. P. (1993). Role of melt water in major river systems of Nepal. IAHS Publications-Publications of the International Association of Hydrological Sc., 218, 113-122.

Butt, M. J., & Bilal, M. (2011). Application of snowmelt runoff model for water resource management. HydrologicalProcesses, 25(24), 3735-3747.

Bashir, F., & Rasul, G. (2010). Estimation of water discharge from Gilgit Basin using remote sensing, GIS and runoff modeling. Pakistan J. Meteor, 6(12), 97-113.

Ashraf, A., Ahmad, S. S., Aziz, N., & Shah, M. T. A. (2012). Preliminary Estimation of Snow Covers Extents of Astore River Basin in Northern Areas, Pakistan. Journal of Geography and Geology, 4(2), p124.

Singh, P., & Bengtsson, L. (2003). Effect of warmer climate on the depletion of snowcovered area in the Satluj basin in the western Himalayan region. Hydrological sciences journal, 48(3), 413-425.

Dey, B., Goswami, D. C., & Rango, A. (1983). Utilization of satellite snow-cover observations for seasonal stream flow estimates in the Western Himalayas. Nordic hydrology, 14(5), 257-266.

Tahir, A. A., Chevallier, P., Arnaud, Y., Neppel, L., & Ahmad, B. (2011). Modeling snowmeltrunoff under climate scenarios in the Hunza River basin, Karakoram Range, Northern Pakistan. Jr. of Hydrology, 409(1), 104-117.

Martinec, J., & Rango, A. (1986). Parameter values for snowmelt runoff modelling. Journal of Hydrology, 84(3), 197-219.

Georgievsky, M. V. (2009). Application of the Snowmelt Runoff model in the Kuban river basin using MODIS satellite images. Environmental Research Letters, 4(4), 045017.

Martinec, J., Rango, A., Roberts, R., 2007. Snowmelt-Runoff Model (SRM) user’s manual. USDA Jornada Experimental Range, New Mexico State University, LasCruces, NM 88003, USA

WMO, 1992. Simulated Real-time Intercomparison of Hydrological Models, Geneva, Switzerland

Tachikawa, T., M. Hato, M. Kaku, A. Iwasaki (2011): Characteristics of ASTER GDEM Version 2. IEEE International Geoscience and Remote Sensing Symposium (IGARSS) 2011, Vancouver, Canada. https://lpdaac.usgs.gov/sites/default/files/public/ aster/docs/Tachikawa_etal_IGARSS_2011.pdf

Riggs, G. A., Hall, D. K., & Salomonson, V. V. (2006). MODIS snow products user guide to collection 5. Digital Media, 80.

Artan, G., Gadain, H., Smith, J. L., Asante, K., Bandaragoda, C. J., & Verdin, J. P. (2007). Adequacy of satellite derived rainfall data for stream flow modeling. Natural Hazards, 43(2), 167-185.

Anderson, J. R. (1976). A land use and land cover classification system for use with remote sensor data (Vol. 964). US Government Printing Office.

Qamer, F. M., Abbas, S., Saleem, R., Shehzad, K., Ali, H., & Gilani, H. (2012). Forest cover change assessment in conflict-affected areas of northwest Pakistan: The case of Swat and Shangla Districts. Journal of Mountain Science, 9(3), 297-306.