Hamming Index for Some Classes of Graphs with Respect to Edge-Vertex Incidence Matrix
Abstract
Hamming distance of a two bit strings u and v of length n is defined to be the number of positions of u and v with different digit. If G is a simple graph on n vertices and m edges and B is an edge–vertex incidence matrix of G, then every edge e of G can be labeled using a binary digit string of length n from the row of B which corresponds to the edge e. We discuss Hamming distance of two different edges of the graph G. Then, we present formulae for the sum of all Hamming distances between two different edges of G, particularly when G is a path, a cycle, and a wheel, and some composite graphs.
Keywords
Citation
Sitorus, W., Suwilo, S. and Mardiningsih, (2018), "Hamming Index for Some Classes of Graphs with Respect to Edge-Vertex Incidence Matrix", Proceedings of MICoMS 2017 (Emerald Reach Proceedings Series, Vol. 1), Emerald Publishing Limited, Leeds, pp. 621-628. https://doi.org/10.1108/978-1-78756-793-1-00098
Publisher
:Emerald Publishing Limited
Copyright © 2018, Wilda Sitorus, Saib Suwilo, Mardiningsih.
License
Published in the Emerald Reach Proceedings Series. Published by Emerald Publishing Limited. This article is published under the Creative Commons Attribution (CC BY 4.0) licence. Anyone may reproduce, distribute, translate and create derivative works of this article (for both commercial and non-commercial purposes), subject to full attribution to the original publication and authors. The full terms of this licence may be seen at http://creativecommons.org/licences/by/4.0/legalcode
1. Introduction
Let
Let G(V,E) be a simple graph on n vertices and m edges with vertex set
An edge–vertex incidence matrix of a graph G is an
The notion of Hamming distance and sum of Hamming distances of edges of simple graph G is initiated by Ramane et al. (2015). They discuss a general formula for Hamming index of a graph and apply this formula to get the Hamming index of classes of regular graph. Hamming distance and Hamming index of a graph can also be defined using the adjacency matrix of the graph (Ganagi and Ramane, 2016). In this paper, we discuss Hamming distance and sum of Hamming distances of simple graph with respect to its edge–vertex incidence matrix. We especially discuss a way of finding the Hamming index of a graph from the known Hamming index of its subgraph. We first present formulae for Hamming index of some graphs consist of a path or a cycle as its subgraph. We then present a formula for Hamming index of some composite graphs.
2. Necessary background
Let G be a graph with vertex set
We note that by definition, the Hamming index of a graph can be calculated using the formula
The following lemma, due to Ramane et al. (2015), presents a formula for Hamming distance between two edges of a simple graph. We present a simpler proof than in Ramane et al. (2015).
Lemma 2. Let G be a simple graph. Then
Proof. Since every edge of G is incident to exactly two vertices, then for each
Theorem 3. Let G a simple graph on m edges. If there are n(P) adjacent pairs of edges in G, then
Proof. By Lemma 2 we have
Proposition 4. Let
Proof. Notice that
Proposition 5. Let
Proof. There are n pairs of adjacent edges
3. Main results
Let G be a graph and F be a subgraph of G. We discuss the Hamming index of the graph G in term of the Hamming index of its subgraph F. We note that
Theorem 6. For a fan
Proof. Notice that a fan
There are
Theorem 7. If
Proof. We note that the cycle
We now conclude that
Theorem 8. If
Proof. Notice that an n-wheel
We now conclude that
Theorem 9. If
Proof. Notice that the cycle
Theorem 10. Let
Proof. If pairs of edges
Let G be a graph on n vertices
Theorem 11. Let G be a graph on n vertices and m edges, then
Proof. If the pair of edges
For
Corollary 12. If
Proof. Notice that
References
Ganagi, A.B. and Ramane, H.S. (2016). “Hamming Distance between the String Generated by Adjacency Matrix of a Graph and their Sum”. Algebra and Discrete Mathematics, Vol. 22, No. 1, pp. 82–93.
Korte, B and Vigen, J. (2006). Combinatorial Optimization Theory and Algorithms. (3rd ed.). Springer, Berlin.
Pless, V. (1998). Introduction to the Theory of Error-Correcting Codes. John Wiley and Sons, Boston.
Ramane, H.S., Joshi, V.B., Jummannaver, R.B., Manjalapur, V.V., Patil, S.C., Shindhe, S.D., Hadimani, V.S., Kyalkonda, V.K. and Baddi, B.C. (2015). “Hamming Index of a Graph Generated by and Edge-Vertex Incidence Matrix”. International Journal of Mathematics, Science. and Engineeringg Application, Vol. 9, No. I, pp. 93–103.
Corresponding author
- Prelims
- Introduction
- Acknowledgement I
- Acknowledgement II
- The Effect of Job Satisfaction and Work Motivation on Organizational Commitment and Organizational Citizenship Behavior in BNI in the Working Area of Bank Indonesia Lhokseumawe
- The Effect of Work Motivation on the Employee Performance with Organization Citizenship Behavior as Intervening Variable at Bank Aceh Syariah
- Life-Cycle Performance of a Bridge Subjected to Multiple Heavy Vehicle Impacts
- The Efforts of Improving the Professionalism of Lecturers towards the Presentation and Change of KKNI within the University Environment in Aceh
- Morphological Process of Devayan: An Analysis of Morphological Tipology
- Effect of Freight Transportation for Regional Development in the North Zone of Aceh
- The Roles of Digital Democracy on Political Education for Young Generation
- Disorders of Sex Development: Ambiguous Genitalia and Partial Androgen Insensitivity Syndrome
- Difference Analysis of the Autonomy of Extended Regencies in Aceh Province Indonesia
- An analysis of Service Quality on Mustahiq Satification using the Kano Model (Case Study on Baitul Mal)
- Exploration and Morphological Characterization of Vegetative Part of Avocado at Bebesan Subdistrict Central Aceh District, Indonesia
- Poverty Effectiveness for the Maisir (Contest) in the City of Indonesian Aceh Province
- Measurement of Study Productivity and Evaluation Analysis by using the American Productivity Center (APC) Model at a Palm Oil Factory (Pks PT. Syaukath Sejahtera)
- The Development of an Independent Entrepreneurship Model Through Creative Economy for Women in Lhokseumawe City
- Regionalism of Aceh’s Traditional Architecture at Bujang Salim Mosque at Krueng Geeukeuh, Aceh
- High Growth and Diameter of the Stem of Corn Plants (Zea May, S) with a Different Cropping Pattern
- Influence of Manufacture of Textiles, Clothing, and Leather and Manufacture of Paper, Printing, and Publishing on Economic Growth
- Land Erodibility and Land use Directions in Krueng Seulimum Watershed Aceh Province
- The Effect of Fermentation of the Peel of Arabica Coffee with Win Prob Probiotics on Crude Fiber Content and Fiber Fraction
- Teaching English International Lingua Franca (ELF) in ASEAN Economic Community Context: Teachers and Students Perspectives
- Animation as a Creative Industry: A Strategy to Build Creativity and Independence of Youth in Padang, West Sumatra
- Improving Production of Liquid Smoke from Candlenut Shell by Pyrolisis Process
- Interpersonal Communication of Commercial Sex Workers Transaction with Customers in Syariah Law Area in Indonesia
- Macrozoobentos Diversity Index as a Bioindicator in Krueng Cunda River to Support the Success of the Shrimp Agribusniness at Lhokseumawe City, Aceh
- The Examination Model of Aceh Commodity Export Firms’ Performance
- The Role of Fishing Techniques with Tuah Teng on Food Security in Facing the Asean Economic Community
- Reconstruction of Aceh Cultural Identity in the Discourse of Aceh Language Lesson Books in Elementary School
- The Effect of Monosodium Glutamate (Msg) Administration to Pyramidal Cells Necrosis on Cerebral Cortex of Wistar Male Rats (Rattus Norvegicus)
- Personal Construct Experience of Tionghoa Community in Aceh Reality
- Study of Mineralogy Composition, Total, and Exchangable Content of K, Ca, and Mg of Volcanic Ash from Sinabung Mountain Eruption in North Sumatera, Indonesia
- The Role of Law in Economic Development: To Develop a Special Economic Zone in Order to Build a National and Regional Economy
- Model Corporate Social Responsibility Based on Local Wisdom in West Aceh Regency
- Recurrence of Intravenous Leiomyomatosis: A Rare Cause of the Obstruction of the Right Heart
- Single Mother Role in The Success of Their Children (Phenomenological Study of Single Women in Makassar City)
- Optimal Lot-Sizing Algorithms on Stochastic Demand at the Retailer
- Predict Environmental Conditions Using Groundwater Interpretation in Subdistrict Hamparan Perak, Deli Serdang, North Sumatera
- Public Discovery of the Concept of Time Value ofMoney with Economic Value of Time
- Study on Impact Strength Against Welding Smaw on Hardening Steel AISI 1050
- What is the Determinant of Non-Performing Financing in Branch Sharia Regional Bank in Indonesia
- Spatial Stochastic Modeling of Adolescent and Under-Five Children Nutritional Status: A Case Study from Aceh, Sumatera Island, Indonesia
- Religious Tourism: Concept of Community-Based TourisminAceh Singkil, Indonesia
- The Contribution of Revenue and Consumption Cost of Soybean Farmers in Muara Batu Subdistrict Aceh Utara
- The Composition of Women Parliament Members Presence in Local Parliament in Aceh (A Case Study at Provincial Parliament of Aceh Province During the Period of 2014 to 2019)
- Personal Branding Tri Rismaharini the Provision in Media
- Analysis of Factors Affecting the Poverty Level of Farmers Post-Tsunami in Aceh
- Dimension of an Islamic Model Value on the Existence of Syariah Walmart
- Batik Jambi Promotion Based on Social Media in Asean Economics Community
- Islamic Banks in Indonesia: Analysis of Efficiency
- Design of Information Monitoring System Flood Based Internet of Things (IoT)
- Economic Development and Access to Fish Resources: A Review Sociology on Fisherman’s Production Access in Kuala Langsa, Aceh
- Dynamics and Prospect of Wali Nanggroe Institution Post-Conflict in Aceh: Analysis of Policy and Educational Development
- Learning Management of Bahasa in Senior High Schools
- The Difference in the Antimicrobial effect of Katuk Leaf Extract (Sauropus Androgynus (l.) Merr.) Concentration against Escherichia Coli
- City Branding of Denpasar City as a Creative City Through the Denpasar Festival Event
- Semantics Equivalence of Cultural Terms of Meurukon Texts Translated from Acehnese into Indonesian
- Preparation of Activated Carbon From Banana (Musa acuminate L.) peels for Carbon Monoxide Adsorption
- Thermal Behavior of Modified Thermoplastic Starch (TPS) Synthesized from Sago (Metroxylon Sagu) with Diphenylmethane Diisocyanate and Castor Oil
- Typhoid Fever Profiles at Cut Meutia Hospital, North Aceh, Indonesia, in 2016-2017
- Student Radicalism Ideology Prevention Strategy: A Study at an Islamic Boarding School in Jabal Nur, North Aceh, Indonesia
- Implementation of Task-Based Learning for Non-English Students: A Practice in Malikussaleh University
- Design of Wild Animal Detection and Rescue System with Passive Infrared and Ultrasonic Sensor based Microcontroller
- Policy of Educational Budget Aceh Regency
- Foreign Direct Investment Inflow into Aceh province of Indonesia After a Peace Agreement
- Design of Web Based Fire Warning System Using Ethernet Wiznet W5500
- Sari Cincau Ngrayun Equals with Modern Ready-to-Drink Beverage
- The Status of Conservation of Mangroves in the Krueng Reuleng River Area, Leupung, Aceh Besar Regency, Indonesia
- Analysis of Understanding the Level of Vibration and the Wave Concept with a Demonstration Method for Students in SMAN 1 Peureulak, Aceh
- Screening of Volatile Organic Compounds Using Gore-Sorber Method for Predicting Hydrocarbon Generation
- Incorporating Peace Education into Aqidah Akhlak Subject in East Aceh
- Learning Motivation of Peripheral University Students and its Relation with their English Grades
- Thermal Cracking of Low Temperature Conversion on Low Density Polyethylene Plastic Waste for Liquid Hydrocarbon
- Correlation of Lead and Zinc Contents in Sediments And Faunus Ater Against Faunus Ater Density in Reuleung River, Leupung, Aceh Besar
- The Correlation between Stress Level and Degree of Depression in the Elderly at a Nursing Home in Lhokseumawe in the Year 2017
- Effect of Palm Oil Bunches Microfiller on LDPE-recycled Composite Tensile Strength through Melt Blending Process
- CSR and Profitability in IDX Agricultural Subsectors
- The Crown Witness and the Protection of Human Rights in Criminal Law Verification
- Design and Implementation of SCADA Wireless Communication System for Monitoring the Performance of Microhydro Power Plant Based on Protocol AX.25
- Production of Lipid Biomass in Locally Isolated Microalga Cultivated in Palm Oil Mill Effluent (POME)
- An Analysis and Design of a Virtual Collaboration Information System of the Jamu Supply Chain Network Based on a Fair Adaptive Contract
- Adsorption of Manganese (II) Ion in the Water Phase by Citric Acid Activated Carbon of Rice Husk
- Eco-informatics: The Encouragement of Ecological Data Management
- Challenges in Designing ESP Course for First Year Students of Engineering Faculty at Malikussaleh University
- Isotherm and Kinetics of Cd(II) Adsorption by Durian (Durio zibethinus) seed Immobilized into Ca-alginate
- Science, Technology, Engineering, and Mathematics (STEM) Learning on Student’s Science Process Skills and Science Attitudes
- Effect of Perception of Facilities, Intensity of Conduct, and Satisfaction of Tax Payers to Submission of Letter by E-Filing Notice on Tax Service
- Aceh: Conflict Development after the Helsinki Agreement
- The Discretionary Accrual in the Financial Statement of a Public Company in Indonesia: A Literature Review
- Inventory and Morphological Characterization of Durian (Durio Zibethinus) in Langkahan and Sawang Sub-District of North Aceh Indonesia
- Model of Sustainable Electrical Power Management: Lamp Efficacy of the National Street Lighting in North Sumatera Province
- Hamming Index for Some Classes of Graphs with Respect to Edge-Vertex Incidence Matrix
- Electrical Automation of Solar Cell-Based Arduino Uno With 16 × LCD Display
- Concept Designs of Patient Information Security Using e-Health Sensor Shield Platform on Blockchain Infrastructure