Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Kamibeppu, Akira
National Institute of Technology, Kushiro College
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
A note on lower bounds for boxicity of graphs Kamibeppu, Akira
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 12, No 1 (2024): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2024.12.1.12

Abstract

The boxicity of a graph G is the minimum non-negative integer k such that G is isomorphic to the intersection graph of a family of boxes in Euclidean k-space, where a box in Euclidean k-space is the Cartesian product of k closed intervals on the real line. In this short note, we define the fractional boxicity of a graph as the optimum value of the linear relaxation of a covering problem with respect to boxicity, which gives a lower bound for its boxicity.  We show that the fractional boxicity of a graph is at least the lower bounds for boxicity given by Adiga et al. in 2014.  We also present a natural lower bound for fractional boxicity of graphs. The aim of this note is to discuss and focus on “accuracy” rather than “simplicity” of these lower bounds for boxicity as the next step in the work by Adiga et al. 
Co-Authors