For a simple, undirected graph $ G(V, E) $, let $ f $ be an edge labeling $ f $: $ E\rightarrow \{0, 1\} $ such that, for any vertex $ v $ and $ i\in\{0, 1\} $, in the edges incident on $ v $, if the number of the edges labeled $ i $ is more than the number of edges labeled $ 1-i $, then the label of $ v $ is defined by $ i $; $ v $ is not defined otherwise. In a labeling graph of $ G $, let $ i\in\{0, 1\} $, $ e_f(i) = |\{e\in E: f(e) = i\}| $ and $ v_f(i) = |\{v\in V: $ the label of $ v $ is $ i\}| $. After $ f $ runs over all edge labelings satisfying $ |e_{f}(1)-e_{f}(0)| \leq 1 $, the set $ \{|v_f(1)-v_f(0)|: |e_f(1)-e_f(0)|\leq 1\} $ is called the edge-balance index set of graph $ G $, denoted by $ EBI(G) $. In this paper, the set $ \{v_f(1)-v_f(0): |e_f(1)-e_f(0)|\leq 1\} $ is called the full edge-balance index set of graph $ G $, denoted by $ FEBI(G) $. Some results are obtained on $ FEBI(G) $, and the relationship between $ FEBI(G) $ and $ EBI(G) $ is discussed. By finding some closed trails, the $ FEBI $ and $ EBI $ of some classes of cubic graphs are obtained.
Citation: Zhen-Bin Gao, Juan Chen, Feng-Xia Chen, Feng Liang. The edge balance properties of cubic graphs[J]. AIMS Mathematics, 2026, 11(2): 5192-5218. doi: 10.3934/math.2026212
For a simple, undirected graph $ G(V, E) $, let $ f $ be an edge labeling $ f $: $ E\rightarrow \{0, 1\} $ such that, for any vertex $ v $ and $ i\in\{0, 1\} $, in the edges incident on $ v $, if the number of the edges labeled $ i $ is more than the number of edges labeled $ 1-i $, then the label of $ v $ is defined by $ i $; $ v $ is not defined otherwise. In a labeling graph of $ G $, let $ i\in\{0, 1\} $, $ e_f(i) = |\{e\in E: f(e) = i\}| $ and $ v_f(i) = |\{v\in V: $ the label of $ v $ is $ i\}| $. After $ f $ runs over all edge labelings satisfying $ |e_{f}(1)-e_{f}(0)| \leq 1 $, the set $ \{|v_f(1)-v_f(0)|: |e_f(1)-e_f(0)|\leq 1\} $ is called the edge-balance index set of graph $ G $, denoted by $ EBI(G) $. In this paper, the set $ \{v_f(1)-v_f(0): |e_f(1)-e_f(0)|\leq 1\} $ is called the full edge-balance index set of graph $ G $, denoted by $ FEBI(G) $. Some results are obtained on $ FEBI(G) $, and the relationship between $ FEBI(G) $ and $ EBI(G) $ is discussed. By finding some closed trails, the $ FEBI $ and $ EBI $ of some classes of cubic graphs are obtained.
| [1] | D. Bouchard, P. Clark, H. H. Su, On edge-balance index sets of L-product of cycles, J. Indones. Math. Soc., 2011, 27–38. https://doi.org/10.22342/jims.0.0.16.27-38 |
| [2] | D. Bouchard, P. Clark, H. H. Su, On edge-balance index sets of L-product of cycles with stars, Part Ⅱ, JCMCC, 82 (2012), 199–209. |
| [3] | J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., 6 (2020). |
| [4] |
R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait colorable, Am. Math. Mon., 82 (1975), 221–239. https://doi.org/10.1080/00029890.1975.11993805 doi: 10.1080/00029890.1975.11993805
|
| [5] | H. Kwong, S. M. Lee, On edge-balance index sets of generalized theta graphs, Congr. Numer., 198 (2009), 157–168. |
| [6] |
M. E. Watkins, A theorem on tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory, 6 (1969), 152–164. https://doi.org/10.1016/S0021-9800(69)80116-X doi: 10.1016/S0021-9800(69)80116-X
|
Figures(6)
Zhen-Bin Gao, Juan Chen, Feng-Xia Chen, Feng Liang. The edge balance properties of cubic graphs[J]. AIMS Mathematics, 2026, 11(2): 5192-5218. doi: 10.3934/math.2026212
DownLoad: